Рубрики

Считать установленные биты в целое число

Напишите эффективную программу для подсчета числа 1 с в двоичном представлении целого числа.

Примеры :

Input : n = 6
Output : 2
Binary representation of 6 is 110 and has 2 set bits

Input : n = 13
Output : 3
Binary representation of 13 is 1101 and has 3 set bits

1. Простой метод. Переберите все биты в целом числе, проверьте, установлен ли бит, и увеличивает ли он установленный счетчик битов. Смотрите ниже программу.

C ++

// C ++ программа для подсчета
// биты в целом числе
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция, чтобы получить не из установленных битов в двоичном
представление положительного целого числа n * /

unsigned int countSetBits(unsigned int n)

{

    unsigned int count = 0;

    while (n) {

        count += n & 1;

        n >>= 1;

    }

    return count;

}

  
/ * Программа для тестирования функции countSetBits * /

int main()

{

    int i = 9;

    cout << countSetBits(i);

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

// Программа C для подсчета
// биты в целом числе
#include <stdio.h>

  
/ * Функция, чтобы получить не из установленных битов в двоичном

   представление положительного целого числа n * /

unsigned int countSetBits(unsigned int n)

{

    unsigned int count = 0;

    while (n) {

        count += n & 1;

        n >>= 1;

    }

    return count;

}

  
/ * Программа для тестирования функции countSetBits * /

int main()

{

    int i = 9;

    printf("%d", countSetBits(i));

    return 0;

}

Джава

// Java-программа для подсчета
// биты в целом числе

import java.io.*;

  

class countSetBits {

    / * Функция, чтобы получить не из набора

    биты в двоичном представлении

    целое положительное число n * /

    static int countSetBits(int n)

    {

        int count = 0;

        while (n > 0) {

            count += n & 1;

            n >>= 1;

        }

        return count;

    }

  

    // драйверная программа

    public static void main(String args[])

    {

        int i = 9;

        System.out.println(countSetBits(i));

    }

}

  
// Этот код предоставлен Аншикой Гоял.

python3

# Python3 программа для подсчета
# бит в целом числе

  
# Функция для получения не установленных битов в двоичном
# представление положительного целого числа n * /

def  countSetBits(n):

    count = 0

    while (n):

        count += n & 1

        n >>= 1

    return count

  

  
# Программа для тестирования функции countSetBits * /

i = 9

print(countSetBits(i))

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// C # программа для подсчета
// биты в целом числе

using System;

  

class GFG {

    // Функция, чтобы получить не из набора

    // биты в двоичном представлении

    // из положительного целого числа n

    static int countSetBits(int n)

    {

        int count = 0;

        while (n > 0) {

            count += n & 1;

            n >>= 1;

        }

        return count;

    }

  

    // Код драйвера

    public static void Main()

    {

        int i = 9;

        Console.Write(countSetBits(i));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP-программа для подсчета
// биты в целом числе

  
// Функция, чтобы получить не из набора
// биты в двоичном представлении
// из положительного целого числа n

function countSetBits($n)

{

    $count = 0;

    while ($n)

    {

        $count += $n & 1;

        $n >>= 1;

    }

    return $count;

}

  
// Код драйвера

$i = 9;

echo countSetBits($i);

  
// Этот код предоставлен ajit
?>


Выход :

2

Сложность времени: (-) (logn) (тэта logn)

Рекурсивный подход:

C ++

// cpp реализация рекурсивного
// подход к поиску номера
// из установленных битов в двоичном представлении
// из положительного целого числа n
#include <bits/stdc++.h>

using namespace std;

  
// рекурсивная функция для подсчета установленных бит

int countSetBits(int n)

{

    // базовый вариант

    if (n == 0)

        return 0;

  

    else

  

        // если последний бит установлен, добавить 1, иначе добавить 0

        return (n & 1) + countSetBits(n >> 1);

}

  
// код драйвера

int main()

{

    // получить значение от пользователя

    int n = 9;

  

    // вызов функции

    cout << countSetBits(n);

  

    return 0;

}

  
// Этот код предоставлен Раджем.

Джава

// Java-рекурсивная реализация
// подход к поиску номера
// из установленных битов в двоичном представлении
// из положительного целого числа n

import java.io.*;

  

class GFG {

  

    // рекурсивная функция для подсчета установленных бит

    public static int countSetBits(int n)

    {

  

        // базовый вариант

        if (n == 0)

            return 0;

  

        else

  

            // если последний бит установлен, добавить 1, иначе добавить 0

            return (n & 1) + countSetBits(n >> 1);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

  

        // получить значение от пользователя

        int n = 9;

  

        // вызов функции

        System.out.println(countSetBits(n));

    }

}

  
// Этот код помогает sunnysingh

python3

# Реализация рекурсивной Python3
# подход, чтобы найти номер набора
# бит в двоичном представлении
# положительное целое число n

  

def countSetBits( n):

      

    # базовый вариант

    if (n == 0):

        return 0

  

    else:

  

        # если последний бит установлен, добавьте еще 1

        # добавить 0

        return (n & 1) + countSetBits(n >> 1)

          
# Получить значение от пользователя

n = 9

  
# Вызов функции

print( countSetBits(n))     

          
# Этот код предоставлен sunnysingh

C #

// C # реализация рекурсивного
// подход к поиску номера
// устанавливаем биты в двоичном представлении
// из положительного целого числа n

using System;

  

class GFG {

  

    // рекурсивная функция

    // посчитать установленные биты

    public static int countSetBits(int n)

    {

  

        // базовый вариант

        if (n == 0)

            return 0;

  

        else

  

            // если последний бит установлен

            // добавить 1 еще добавить 0

            return (n & 1) + countSetBits(n >> 1);

    }

  

    // Код драйвера

    static public void Main()

    {

  

        // получить значение

        // от пользователя

        int n = 9;

  

        // вызов функции

        Console.WriteLine(countSetBits(n));

    }

}

  
// Этот код предоставлен aj_36

PHP

<?php
// рекурсивная реализация PHP
// подход к поиску номера
// устанавливаем биты в двоичном представлении
// из положительного целого числа n

  
// рекурсивная функция
// посчитать установленные биты

function countSetBits($n)

{

    // базовый вариант

    if ($n == 0)

        return 0;

  

    else

  

        // если последний бит установлен

        // добавить 1 еще добавить 0

        return ($n & 1) + 

                countSetBits($n >> 1);

}

  
// Код драйвера

  
// получить значение от пользователя

$n = 9;

  
// вызов функции

echo countSetBits($n);

  
// Этот код предоставлен m_kit.
?>


Выход :

2

2. Алгоритм Брайана Кернигана:
Вычитание 1 из десятичного числа переворачивает все биты после самого правого установленного бита (который равен 1), включая самый правый установленный бит.
например :
10 в двоичном виде — 00001010
9 в двоичном виде — 00001001
8 в двоичном виде — 00001000
7 в двоичном виде — 00000111
Так что, если мы вычтем число на 1 и сделаем поразрядно & с самим собой (n & (n-1)), мы сбросим самый правый установленный бит. Если мы выполним n & (n-1) в цикле и посчитаем число выполнений цикла no of times, мы получим установленное количество битов.
Прелесть этого решения в том, что количество циклов равно количеству установленных бит в данном целом числе.

 
   1  Initialize count: = 0
   2  If integer n is not zero
      (a) Do bitwise & with (n-1) and assign the value back to n
          n: = n&(n-1)
      (b) Increment count by 1
      (c) go to step 2
   3  Else return count
 

Реализация алгоритма Брайана Кернигана:

C ++

// C ++ программа для подсчета
// биты в целом числе
#include <iostream>

using namespace std;

class gfg {

    / * Функция, чтобы получить не из установленных битов в двоичном

представление переданного двоичного кода * /

public:

    unsigned int countSetBits(int n)

    {

        unsigned int count = 0;

        while (n) {

            n &= (n - 1);

            count++;

        }

        return count;

    }

};
/ * Программа для тестирования функции countSetBits * /

int main()

{

    gfg g;

    int i = 9;

    cout << g.countSetBits(i);

    return 0;

}

С

// Программа C для подсчета
// биты в целом числе
#include <stdio.h>

  
/ * Функция, чтобы получить не из установленных битов в двоичном

   представление переданного двоичного кода * /

unsigned int countSetBits(int n)

{

    unsigned int count = 0;

    while (n) {

        n &= (n - 1);

        count++;

    }

    return count;

}

  
/ * Программа для тестирования функции countSetBits * /

int main()

{

    int i = 9;

    printf("%d", countSetBits(i));

    getchar();

    return 0;

}

Джава

// Java-программа для подсчета
// биты в целом числе

import java.io.*;

  

class countSetBits {

    / * Функция, чтобы получить не из набора

    биты в двоичном представлении

    из переданного двоичного № * /

    static int countSetBits(int n)

    {

        int count = 0;

        while (n > 0) {

            n &= (n - 1);

            count++;

        }

        return count;

    }

  

    // драйверная программа

    public static void main(String args[])

    {

        int i = 9;

        System.out.println(countSetBits(i));

    }

}

  
// Этот код предоставлен Аншикой Гоял.

python3

# Функция для получения не установленных битов в двоичном
# представление переданного двоичного кода * /

def countSetBits(n):

  

    count = 0

    while (n):

        n &= (n-1

        count+= 1

      

    return count

  

  
# Программа для тестирования функции countSetBits

i = 9

print(countSetBits(i))

   
# Этот код предоставлен
# Смита Динеш Семвал

C #

// C # программа для подсчета
// биты в целом числе

using System;

  

class GFG {

  

    / * Функция, чтобы получить не из набора

    биты в двоичном представлении

    из переданного двоичного № * /

    static int countSetBits(int n)

    {

        int count = 0;

        while (n > 0) {

            n &= (n - 1);

            count++;

        }

        return count;

    }

  

    // Код драйвера

    static public void Main()

    {

        int i = 9;

        Console.WriteLine(countSetBits(i));

    }

}

  
// Этот код предоставлен ajit

PHP

<?php

  
/ * Функция, чтобы не получить
установить биты в двоичном
представление прошло
двоичный номер * /

function countSetBits($n)

{

    $count = 0;

    while ($n)

    {

    $n &= ($n - 1) ;

    $count++;

    }

    return $count;

}

  
// Код драйвера

$i = 9;

echo countSetBits($i);

  
// Этот код добавлен
// от akt_mit
?>


Выход :

2

Пример для алгоритма Брайана Кернигана:

   n =  9 (1001)
   count = 0

   Since 9 > 0, subtract by 1 and do bitwise & with (9-1)
   n = 9&8  (1001 & 1000)
   n = 8
   count  = 1

   Since 8 > 0, subtract by 1 and do bitwise & with (8-1)
   n = 8&7  (1000 & 0111)
   n = 0
   count = 2

   Since n = 0, return count which is 2 now.

Сложность времени: O (logn)

Рекурсивный подход:

C ++

// Реализация CPP для рекурсивного
// подход к поиску номера набора
// биты с использованием алгоритма Брайана Кернигана
#include <bits/stdc++.h>

using namespace std;

  
// рекурсивная функция для подсчета установленных бит

int countSetBits(int n)

{

    // базовый вариант

    if (n == 0)

        return 0;

    else

        return 1 + countSetBits(n & (n - 1));

}

  
// код драйвера

int main()

{

    // получить значение от пользователя

    int n = 9;

  

    // вызов функции

    cout << countSetBits(n);

  

    return 0;

}

  
// Этот код предоставлен Раджем.

Джава

// Реализация Java для рекурсивного
// подход к поиску номера набора
// биты с использованием алгоритма Брайана Кернигана

import java.io.*;

  

class GFG {

  

    // рекурсивная функция для подсчета установленных бит

    public static int countSetBits(int n)

    {

  

        // базовый вариант

        if (n == 0)

            return 0;

        else

            return 1 + countSetBits(n & (n - 1));

    }

  

    // Функция драйвера

    public static void main(String[] args)

    {

  

        // получить значение от пользователя

        int n = 9;

  

        // вызов функции

        System.out.println(countSetBits(n));

    }

}

  
// Этот код предоставлен sunnysingh

python3

# Реализация Python3 для
# рекурсивный подход к поиску
# число установленных битов
Алгоритм Брайана Кернигана

  
# рекурсивная функция для подсчета
# установить биты

def countSetBits(n):

  

    # базовый вариант

    if (n == 0):

        return 0

    else:

        return 1 + countSetBits(n & (n - 1))

              

              
# Получить значение от пользователя

n = 9

      
# вызов функции

print(countSetBits(n))

  
# Этот код предоставлен sunnysingh

C #

// C # реализация для рекурсии
// подход к поиску номера набора
// биты с использованием алгоритма Брайана Кернигана

using System;

  

class GFG {

  

    // рекурсивная функция

    // посчитать установленные биты

    public static int countSetBits(int n)

    {

  

        // базовый вариант

        if (n == 0)

            return 0;

        else

            return 1 + countSetBits(n & (n - 1));

    }

  

    // Код драйвера

    static public void Main()

    {

  

        // получить значение от пользователя

        int n = 9;

  

        // вызов функции

        Console.WriteLine(countSetBits(n));

    }

}

  
// Этот код предоставлен aj_36

PHP

<?php
// Реализация PHP для
// рекурсивный подход к
// найти номер набора
// биты с использованием Брайана
// Алгоритм Кернигана

  
// рекурсивная функция для
// считать установленные биты

function countSetBits($n)

{

    // базовый вариант

    if ($n == 0)

        return 0;

    else

        return 1 + 

          countSetBits($n

                      ($n - 1));

}

  
// Код драйвера

  
// получить значение от пользователя

$n = 9;

  
// вызов функции

echo countSetBits($n);

      
// Этот код предоставлен ajit.
?>


Выход :

2

3. Использование таблицы поиска: мы можем считать биты за O (1) время, используя таблицу поиска. Пожалуйста, смотрите http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable для деталей.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  

int BitsSetTable256[256];

  
// Функция для инициализации таблицы поиска

void initialize() 

  

    // Для первоначальной генерации

    // таблица алгоритмически

    BitsSetTable256[0] = 0; 

    for (int i = 0; i < 256; i++)

    

        BitsSetTable256[i] = (i & 1) + 

        BitsSetTable256[i / 2]; 

    

  
// Функция для возврата счета
// из установленных битов в n

int countSetBits(int n) 

    return (BitsSetTable256[n & 0xff] + 

            BitsSetTable256[(n >> 8) & 0xff] + 

            BitsSetTable256[(n >> 16) & 0xff] + 

            BitsSetTable256[n >> 24]); 

  
// Код драйвера

int main() 

    // Инициализируем таблицу поиска

    initialize(); 

    int n = 9; 

    cout << countSetBits(n);

  
// Этот код предоставлен Sanjit_Kumar

Джава

// Java реализация подхода

class GFG {

  

    // Справочная таблица

    static int[] BitsSetTable256 = new int[256];

  

    // Функция для инициализации таблицы поиска

    public static void initialize()

    {

  

        // Для первоначальной генерации

        // таблица алгоритмически

        BitsSetTable256[0] = 0;

        for (int i = 0; i < 256; i++) {

            BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];

        }

    }

  

    // Функция для возврата счета

    // из установленных битов в n

    public static int countSetBits(int n)

    {

        return (BitsSetTable256[n & 0xff]

                + BitsSetTable256[(n >> 8) & 0xff]

                + BitsSetTable256[(n >> 16) & 0xff]

                + BitsSetTable256[n >> 24]);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

  

        // Инициализируем таблицу поиска

        initialize();

        int n = 9;

        System.out.print(countSetBits(n));

    }

}

Выход:

2

Мы можем найти одно использование подсчета установленных битов в Count количество битов, которое нужно перевернуть, чтобы преобразовать A в B

Примечание. В GCC мы можем напрямую считать установленные биты с помощью __builtin_popcount (). Таким образом, мы можем избежать отдельной функции для подсчета установленных битов.

C ++

// C ++ программа для демонстрации __builtin_popcount ()
#include <iostream>

using namespace std;

  

int main()

{

    cout << __builtin_popcount(4) << endl;

    cout << __builtin_popcount(15);

  

    return 0;

}

Джава

// Java-программа для демонстрации
// __builtin_popcount ()

  

import java.io.*;

  

class GFG {

  

    // Код драйвера

    public static void main(String[] args)

    {

  

        System.out.println(Integer.bitCount(4));

        System.out.println(Integer.bitCount(15));

    }

}

  
// Этот код предоставлен Раджем

python3

# Python3 программа для демонстрации __builtin_popcount ()

  

print(bin(4).count('1'));

print(bin(15).count('1'));

  
# Этот код предоставлен mits

C #

// C # программа для демонстрации
// __builtin_popcount ()

using System;

using System.Linq;

  

class GFG {

  

    // Код драйвера

    public static void Main()

    {

  

        Console.WriteLine(Convert.ToString(4, 2).Count(c = > c == '1'));

        Console.WriteLine(Convert.ToString(15, 2).Count(c = > c == '1'));

    }

}

  
// Этот код предоставлен mits

PHP

<?php
// PHP программа для демонстрации
// __builtin_popcount ()

  
// Код драйвера

$t = log10(4);

$x = log(15, 2);

$tt = ceil($t);

$xx = ceil($x);

  

echo ($tt), "\n";

echo ($xx), "\n";

  
// Этот код добавлен
// от jit_t
?>


Выход :

1
4

4. Отображение чисел с битом. Он просто поддерживает карту (или массив) чисел в битах для клева. Клев содержит 4 бита. Итак, нам нужен массив до 15.
int num_to_bits [16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
Теперь нам нужно только рекурсивно получить кусочки заданного long / int / word и т. Д.

C ++

// C ++ программа для подсчета установленных битов путем предварительного сохранения
// считать установленные биты в клевах.
#include <bits/stdc++.h>

using namespace std;

  

int num_to_bits[16] = { 0, 1, 1, 2, 1, 2, 2, 3,

                        1, 2, 2, 3, 2, 3, 3, 4 };

  
/ * Рекурсивно получить кусочек заданного числа
и отобразить их в массиве * /

unsigned int countSetBitsRec(unsigned int num)

{

    int nibble = 0;

    if (0 == num)

        return num_to_bits[0];

  

    // Найти последний клев

    nibble = num & 0xf;

  

    // Используем предварительно сохраненные значения, чтобы найти количество

    // в последнем клеве плюс рекурсивное добавление

    // оставшиеся кусочки

    return num_to_bits[nibble] + countSetBitsRec(num >> 4);

}

  
// Код драйвера

int main()

{

    int num = 31;

    cout << countSetBitsRec(num);

    return 0;

}

  
// Этот код предоставлен rathbhupendra

С

// C программа для подсчета установленных бит путем предварительного сохранения
// считать установленные биты в клевах.
#include <stdio.h>

  

int num_to_bits[16] = { 0, 1, 1, 2, 1, 2, 2, 3,

                        1, 2, 2, 3, 2, 3, 3, 4 };

  
/ * Рекурсивно получить кусочек заданного числа

  и отобразить их в массиве * /

unsigned int countSetBitsRec(unsigned int num)

{

    int nibble = 0;

    if (0 == num)

        return num_to_bits[0];

  

    // Найти последний клев

    nibble = num & 0xf;

  

    // Используем предварительно сохраненные значения, чтобы найти количество

    // в последнем клеве плюс рекурсивное добавление

    // оставшиеся кусочки

    return num_to_bits[nibble] + countSetBitsRec(num >> 4);

}

  
// Код драйвера

int main()

{

    int num = 31;

    printf("%d\n", countSetBitsRec(num));

}

Джава

// Java-программа для подсчета установленных битов путем предварительного сохранения
// считать установленные биты в клевах.

  

class GFG {

    static int[] num_to_bits = new int[] { 0, 1, 1, 2, 1, 2, 2,

                                           3, 1, 2, 2, 3, 2, 3, 3, 4 };

  

    / * Рекурсивно получить кусочек заданного числа

и отобразить их в массиве * /

    static int countSetBitsRec(int num)

    {

        int nibble = 0;

        if (0 == num)

            return num_to_bits[0];

  

        // Найти последний клев

        nibble = num & 0xf;

  

        // Используем предварительно сохраненные значения, чтобы найти количество

        // в последнем клеве плюс рекурсивное добавление

        // оставшиеся кусочки

        return num_to_bits[nibble] + countSetBitsRec(num >> 4);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int num = 31;

        System.out.println(countSetBitsRec(num));

    }

}
// этот код предоставлен mits

python3

# Python3 программа для подсчета установленных битов путем предварительного сохранения
# количество установленных бит в клевах.

  

num_to_bits =[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]; 

  
# Рекурсивно получить кусочек заданного числа
# и сопоставить их в массиве

def countSetBitsRec(num):

    nibble = 0;

    if(0 == num):

        return num_to_bits[0];

      

    # Найти последний клев

    nibble = num & 0xf;

      

    # Используйте предварительно сохраненные значения, чтобы найти количество

    # в последнем клеве плюс рекурсивное добавление

    # оставшиеся клев.

      

    return num_to_bits[nibble] + countSetBitsRec(num >> 4); 

   

  
# Код драйвера

   

num = 31

print(countSetBitsRec(num)); 

  

  
# этот код предоставлен mits

C #

// C # программа для подсчета установленных бит путем предварительного сохранения
// считать установленные биты в клевах.

  

class GFG {

    static int[] num_to_bits = new int[16] { 0, 1, 1, 2, 1, 2, 2,

                                             3, 1, 2, 2, 3, 2, 3, 3, 4 };

  

    / * Рекурсивно получить кусочек заданного числа

и отобразить их в массиве * /

    static int countSetBitsRec(int num)

    {

        int nibble = 0;

        if (0 == num)

            return num_to_bits[0];

  

        // Найти последний клев

        nibble = num & 0xf;

  

        // Используем предварительно сохраненные значения, чтобы найти количество

        // в последнем клеве плюс рекурсивное добавление

        // оставшиеся кусочки

        return num_to_bits[nibble] + countSetBitsRec(num >> 4);

    }

  

    // Код драйвера

    static void Main()

    {

        int num = 31;

        System.Console.WriteLine(countSetBitsRec(num));

    }

}
// этот код предоставлен mits

PHP

<?php
// PHP-программа для подсчета установленных бит
// предварительно сохраняем количество битов в полубайтах.

  

$num_to_bits = array(0, 1, 1, 2, 1, 2, 2, 3,

                     1, 2, 2, 3, 2, 3, 3, 4); 

  
/ * Рекурсивно получить кусочек заданного
номер и отобразить их в массиве * /

function countSetBitsRec( $num

    global $num_to_bits;

    $nibble = 0; 

    if (0 == $num

        return $num_to_bits[0]; 

      

    // Найти последний клев

    $nibble = $num & 0xf; 

      

    // Используем предварительно сохраненные значения, чтобы найти количество

    // в последнем клеве плюс рекурсивное добавление

    // оставшиеся кусочки

    return $num_to_bits[$nibble] + 

           countSetBitsRec($num >> 4); 

  
// Код драйвера

$num = 31; 

echo (countSetBitsRec($num)); 

  
// Этот код предоставлен mits
?>


Выход :

5

Сложность времени: O (1)
Сложность хранения: O (1) Независимо от того, является ли данное число коротким, целым, длинным или длинным длинным, нам нужен только массив размером 16, который является постоянным.

Подсчет установленных битов в целом числе Использование таблицы поиска

Спросил в: Adobe , Brocade , Cisco , Juniper Networks , Qualcomm

Ссылки:
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Рекомендуемые посты:

Считать установленные биты в целое число

0.00 (0%) 0 votes