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

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

67 голосов | спросил TimeToCodeTheRoad 15 Jpm1000000pmSun, 15 Jan 2012 20:18:44 +040012 2012, 20:18:44

21 ответ


0

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

  

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

ответил Óscar López 15 Jpm1000000pmSun, 15 Jan 2012 20:28:21 +040012 2012, 20:28:21
0

У меня есть решение, которое подсчитывает биты в 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 в двоичном виде), оно будет проверять каждый бит.

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

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

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

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

ответил 0605002 15 Jpm1000000pmSun, 15 Jan 2012 20:48:10 +040012 2012, 20:48:10
0

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

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

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

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

ответил Sriram Mahavadi 18 AM00000010000002331 2013, 01:47:23
0

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

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;
}
ответил user2555279 6 J000000Saturday13 2013, 04:08:50
0
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);
}
ответил akus 31 +04002012-10-31T17:20:55+04:00312012bEurope/MoscowWed, 31 Oct 2012 17:20:55 +0400 2012, 17:20:55
0
   countBits(x){
     y=0;
     while(x){   
       y += x &  1 ;
       x  = x >> 1 ;
     }
   }

это все?

ответил user40521 11 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 11 Sep 2014 09:30:18 +0400 2014, 09:30:18
0

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

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

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

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

ответил alf 15 Jpm1000000pmSun, 15 Jan 2012 20:20:11 +040012 2012, 20:20:11
0

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

nofone(int x) {
  a=0;
  while(x!=0) {
    x>>=1;
    if(x & 1)
      a++;
  }
  return a;
} 
ответил Vigneswaran 11 J000000Thursday13 2013, 17:43:42
0

Функция принимает 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;
}
ответил Roshan 3 Maypm13 2013, 19:23:03
0

Ниже приведено решение C с использованием битовых операторов:

int numberOfOneBitsInInteger(int input) {
  int numOneBits = 0;

  int currNum = input;
  while (currNum != 0) {
    if ((currNum & 1) == 1) {
      numOneBits++;
    }
    currNum = currNum >> 1;
  }
  return numOneBits;
}

Ниже приведено Java-решение с использованием степеней 2:

public static int numOnesInBinary(int n) {

  if (n < 0) return -1;

  int j = 0;
  while ( n > Math.pow(2, j)) j++;

  int result = 0;
  for (int i=j; i >=0; i--){
    if (n >= Math.pow(2, i)) {
        n = (int) (n - Math.pow(2,i));
        result++;    
    }
  }

  return result;
}
ответил eb80 30 J000000Wednesday14 2014, 18:23:22
0

Ниже приведены два простых примера (на C ++), среди которых вы можете сделать это.

  1. Мы можем просто посчитать установленные биты (1), используя __builtin_popcount ().

    int numOfOnes(int x) { return __builtin_popcount(x); }

  2. Циклически перебирайте все биты в целом числе, проверяйте, установлен ли бит и увеличивается ли тогда переменная count.

    int hammingDistance(int x) { int count = 0 for(int i = 0; i < 32; i++) if(x & (1 << i)) count++; return count; }

Надеюсь, это поможет!

ответил Gaurav Sharma 21 WedEurope/Moscow2016-12-21T07:23:04+03:00Europe/Moscow12bEurope/MoscowWed, 21 Dec 2016 07:23:04 +0300 2016, 07:23:04
0

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

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

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

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

ответил Vishwadeep Kapoor 31 SunEurope/Moscow2017-12-31T10:15:20+03:00Europe/Moscow12bEurope/MoscowSun, 31 Dec 2017 10:15:20 +0300 2017, 10:15:20
0

Есть только один способ решить эту задачу в O (1) ... это «обмануть» и использовать физическое устройство (при линейном или даже параллельном программировании я думаю, что предел равен O (log ( k)) где k представляет количество байтов числа).

Однако вы можете легко представить себе физическое устройство, которое подключает каждый бит А к выходной линии с напряжением 0/1. Тогда вы могли бы просто в электронном виде прочитать общее напряжение на линии суммирования в O (1). Было бы довольно просто сделать эту базовую идею более элегантной с помощью некоторых базовых элементов схемы, чтобы получить выход в любой форме, которую вы хотите (например, двоичный кодированный выход), но основная идея такая же, и электронная схема выдаст правильный вывод. состояние в установленное время.

Я полагаю, что возможны также квантовые вычислительные возможности, но если бы нам это позволили, я бы подумал, что простая электронная схема - более простое решение.

ответил Tim Gee 15 Jpm1000000pmSun, 15 Jan 2012 21:52:34 +040012 2012, 21:52:34
0

Я на самом деле сделал это, используя небольшую ловкость рук: одной справочной таблицы с 16 записями будет достаточно, и все, что вам нужно сделать, это разбить двоичный повтор на кусочки (4-битные кортежи). Сложность на самом деле O (1), и я написал шаблон C ++, который специализировался на размере целого числа, которое вы хотели (в # битах) ... делает его постоянным выражением, а не неопределенным.

Между тем, вы можете использовать тот факт, что (i & -i) вернет вам однобитный LS и просто зацикливает, удаляя lsbit каждый раз, пока целое число не станет равным нулю, - но это старый прием контроля четности.

ответил kai26873 17 Jam1000000amTue, 17 Jan 2012 11:09:28 +040012 2012, 11:09:28
0

Я пришел сюда с большим убеждением, что знаю прекрасное решение этой проблемы. Код в C:

    short numberOfOnes(unsigned int d) {
        short count = 0;

        for (; (d != 0); d &= (d - 1))
            ++count;

        return count;
    }

Но после небольшого исследования этой темы (читайте другие ответы :)) я нашел 5 более эффективных алгоритмов. Люблю так!

Существует даже инструкция процессора, разработанная специально для этой задачи: popcnt. (упоминается в этом ответе )

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

ответил naXa 24 AM00000010000003131 2013, 01:48:31
0

Приведенный ниже метод может также подсчитать число 1 в отрицательных числах.

private static int countBits(int number)    {
    int result = 0;
    while(number != 0)  {
        result += number & 1;
        number = number >>> 1;
    }
    return result;
}

Тем не менее, число типа -1 представляется в двоичном виде как 11111111111111111111111111111111 и поэтому потребует большого смещения. Если вы не хотите делать так много смен для маленьких отрицательных чисел, другой способ может быть следующим:

private static int countBits(int number)    {
    boolean negFlag = false;
    if(number < 0)  { 
        negFlag = true;
        number = ~number;
    }

    int result = 0;
    while(number != 0)  {
        result += number & 1;
        number = number >> 1;
    }
    return negFlag? (32-result): result;
}
ответил Menezes Sousa 25 Jam1000000amSun, 25 Jan 2015 00:59:07 +030015 2015, 00:59:07
0

В python или любом другом преобразовании в строку bin, затем разделите ее на '0', чтобы избавиться от 0, затем объедините и получите длину.

len(''.join(str(bin(122011)).split('0')))-1
ответил ben 2 PM00000050000000831 2014, 17:14:08
0

Используя строковые операции JS, можно сделать следующее;

0b1111011.toString(2).split(/0|(?=.)/).length // returns 6

или

0b1111011.toString(2).replace("0","").length  // returns 6
ответил Redu 28 PM00000020000000031 2016, 14:22:00
0

Я должен был сыграть в гольф в рубине и закончил с

l=->x{x.to_s(2).count ?1}

Использование:

l[2**32-1] # returns 32

Очевидно, что неэффективно, но делает свое дело :)

ответил hoang 28 MarpmTue, 28 Mar 2017 17:13:19 +03002017-03-28T17:13:19+03:0005 2017, 17:13:19
0

реализация Ruby

def find_consecutive_1(n)
  num = n.to_s(2)
  arr = num.split("")
  counter = 0
  max = 0
  arr.each do |x|
      if x.to_i==1
          counter +=1
      else
          max = counter if counter > max
          counter = 0 
      end
      max = counter if counter > max  
  end
  max
end

puts find_consecutive_1(439)
ответил Jagdish N 10 AMpMon, 10 Apr 2017 01:35:30 +030035Monday 2017, 01:35:30
0

Два пути ::

/* Method-1 */
int count1s(long num)
{
    int tempCount = 0;

    while(num)
    {
        tempCount += (num & 1); //inc, based on right most bit checked
        num = num >> 1;         //right shift bit by 1
    }

    return tempCount;
}

/* Method-2 */
int count1s_(int num)
{
    int tempCount = 0;

    std::string strNum = std::bitset< 16 >( num ).to_string(); // string conversion
    cout << "strNum=" << strNum << endl;
    for(int i=0; i<strNum.size(); i++)
    {
        if('1' == strNum[i])
        {
            tempCount++;
        }
    }

    return tempCount;
}

/* Method-3 (algorithmically - boost string split could be used) */
1) split the binary string over '1'.
2) count = vector (containing splits) size - 1

Использование ::

    int count = 0;

    count = count1s(0b00110011);
    cout << "count(0b00110011) = " << count << endl; //4

    count = count1s(0b01110110);
    cout << "count(0b01110110) = " << count << endl;  //5

    count = count1s(0b00000000);
    cout << "count(0b00000000) = " << count << endl;  //0

    count = count1s(0b11111111);
    cout << "count(0b11111111) = " << count << endl;  //8

    count = count1s_(0b1100);
    cout << "count(0b1100) = " << count << endl;  //2

    count = count1s_(0b11111111);
    cout << "count(0b11111111) = " << count << endl;  //8

    count = count1s_(0b0);
    cout << "count(0b0) = " << count << endl;  //0

    count = count1s_(0b1);
    cout << "count(0b1) = " << count << endl;  //1
ответил parasrish 23 PMpSun, 23 Apr 2017 16:31:18 +030031Sunday 2017, 16:31:18

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132