Подсчитать количество единиц в двоичном представлении

Question

Эффективный способ подсчета числа 1 с в двоичном представлении числа в O (1), если у вас достаточно памяти для игры.Это вопрос интервью, который я нашел на онлайн-форуме, но на него не было ответа.Может кто-нибудь что-то предложить, я не могу придумать, как это сделать за O (1) раз?

Answer 1

Это проблема веса Хэмминга , он же численность населения.Ссылка упоминает эффективные реализации.Цитата:

С неограниченной памятью мы могли бы просто создать большую справочную таблицу веса Хэмминга из каждого 64-битного целого числа

Answer 2

У меня есть решение, которое считает биты за O(Number of 1's) время:

bitcount(n):
    count = 0
    while n > 0:
        count = count + 1
        n = n & (n-1)
    return count

В худшем случае (когда число равно 2 ^ n - 1, все 1 в двоичном виде) он будет проверять каждый бит.

Edit: Только что нашел очень хороший алгоритм с постоянной и постоянной памятью для bitcount. Вот оно, написанное на C:

int BitCount(unsigned int u)
{
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}

Вы можете найти доказательство его правильности здесь .

Answer 3

Обратите внимание, что: n & (n-1) всегда исключает наименее значимое 1.

Следовательно, мы можем написать код для вычисления количества единиц следующим образом:

count=0;
while(n!=0){
  n = n&(n-1);
  count++;
}
cout<<"Number of 1's in n is: "<<count;

Сложность программы: число единиц в n (которое постоянно <32). </p>

Answer 4

Я видел следующее решение с другого сайта:

int count_one(int x){
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

Answer 5

public static void main(String[] args) {

    int a = 3;
    int orig = a;
    int count = 0;
    while(a>0)
    {
        a = a >> 1 << 1;
        if(orig-a==1)
            count++;
        orig = a >> 1;
        a = orig;
    }

    System.out.println("Number of 1s are: "+count);
}

Answer 6

   countBits(x){
     y=0;
     while(x){   
       y += x &  1 ;
       x  = x >> 1 ;
     }
   }

вот это?

Answer 7

Это будет самый короткий ответ в моей жизни SO: справочная таблица.

Очевидно, мне нужно объяснить немного: "если у вас достаточно памятииграть "значит", у нас есть вся необходимая память (не говоря уже о технической возможности).Теперь вам не нужно хранить таблицу поиска для более чем одного байта или двух.Хотя технически это будет Ω (log (n)), а не O (1), просто для чтения нужного вам числа будет Ω (log (n)), поэтому, если это проблема, то ответ будет невозможно - что еще короче.

Какой из двух ответов они ожидают от вас на собеседовании, никто не знает.

Есть еще одна хитрость: пока инженерыможет взять число и поговорить о Ω (log (n)), где n - это число, компьютерные ученые скажут, что на самом деле мы должны измерить время работы как функцию длины входа,поэтому то, что инженеры называют Ω (log (n)), на самом деле является Ω (k), где k - это число байтов.Тем не менее, как я уже говорил, просто читать число - это Ω (k), поэтому мы никак не можем добиться большего, чем это.

Answer 8

Ниже тоже будет работать.

nofone(int x) {
  a=0;
  while(x!=0) {
    x>>=1;
    if(x & 1)
      a++;
  }
  return a;
} 

Answer 9

Функция принимает int и возвращает количество единиц в двоичном представлении

public static int findOnes(int number)
{

   if(number < 2)
    {
        if(number == 1)
        {
            count ++;
        }
        else
        {
            return 0;
        }
    }

    value = number % 2;

    if(number != 1 && value == 1)
        count ++;

    number /= 2;

    findOnes(number);

    return count;
}

Answer 10

Лучший способ сделать это в javascript - это

function getBinaryValue(num){
 return num.toString(2);
}

function checkOnces(binaryValue){
    return binaryValue.toString().replace(/0/g, "").length;
}

где binaryValue - двоичная строка, например: 1100