Количество 1 в двоичном представлении в O (n) и O (log n), где n - количество бит

Question

У меня две задачи - считать 1 в двоичном представлении в O (n) и O (log n).Поскольку первая часть проста, я не могу понять, как я могу считать их в O (log n), поскольку он не отсортирован или что-то еще.Это вообще возможно?Мой код до сих пор:

public class CountOnes {
  public static void main(String[] args)
  {
    System.out.println("Program to count ones");
    countOnesInLinearTime("110");
    countOnesInlogarithmicTime("110");
  }

  private static void countOnesInlogarithmicTime(String binaryRepresentationOfLong) {
    //TODO
  }

  private static void countOnesInLinearTime(String binaryRepresentationOfLong) {
    int numberOfOnes = 0;
    for(int i = 0; i < binaryRepresentationOfLong.length(); i++)
    {
      if(binaryRepresentationOfLong.charAt(i) == '1')
      {
        numberOfOnes++;
      }
    }
    System.out.println(numberOfOnes);
  }
}

Я нашел: Подсчитать количество единиц в двоичном представлении , но это немного отличается.

Answer 1

Предполагая, что ваша входная строка будет целочисленной, а не строковой, это достигается с помощью алгоритма Брайана Кернигана:

Вычитание 1 из числа переключает все биты (справа налево) до крайнего правого установленного бита (включая крайний правый установленный бит). Поэтому, если мы вычтем число на 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

Осуществление

int countNumberOfOnes(int n) { 
    int count = 0; 
    while (n > 0) { 
        n &= (n - 1); 
        count++; 
    } 
    return count; 
}

Answer 2

Вы можете посчитать количество установленных бит в long следующим образом:

long l = 1425142514251425142L; // some value
long c = l;
c = ((c >> 1) & 0x5555555555555555L) + (c & 0x5555555555555555L);
c = ((c >> 2) & 0x3333333333333333L) + (c & 0x3333333333333333L);
c = ((c >> 4) & 0x0f0f0f0f0f0f0f0fL) + (c & 0x0f0f0f0f0f0f0f0fL);
c = ((c >> 8) & 0x00ff00ff00ff00ffL) + (c & 0x00ff00ff00ff00ffL);
c = ((c >> 16) & 0x0000ffff0000ffffL) + (c & 0x0000ffff0000ffffL);
c = ((c >> 32) & 0x00000000ffffffffL) + (c & 0x00000000ffffffffL);

Мы в основном выполняем O (n) раз, с n количество бит, аналогичная операция.Для i '-го шага (с i, начиная с 1), мы выполняем операцию, подобную:

c = ((c >> 2<sup>i</sup>) & mask) + (c & mask);

Маска имеет двоичную структуру:

0101010101010101
0011001100110011
0000111100001111
0000000011111111
...

Итак, для i -ого шага это повторение 2<sup>i</sup> нулей, за которыми следуют 2<sup>i</sup>, и это повторяется до тех пор, пока мы не достигнем 64 бит.

Как это работает?Сдвигая 2<sup>i</sup> мест вправо, мы «выравниваем» две части числа.Первая часть - это те, которые расположены там, где у mask есть нули, а другая часть - там, где есть маски.Затем мы суммируем два.

На первом шаге это означает, что для каждых двух битов мы выравниваем биты вправо, суммируем их, и результат этой суммы (значение между 0и 2 (оба включительно) могут быть представлены двумя битами.Так что теперь c содержит последовательность из 32 2-битных чисел, каждое из которых представляет сумму числа двух битов.

В следующей итерации мы снова выполняем выравнивание, и теперь мы суммируем 16эти 2-битные числа с соседом слева (то есть с другими 16 2-битными числами), что может привести к значениям от 0 до 4, поэтому мы можем представить это число из 3 битов, но мы используем пробелдля 4 битов.

Таким образом, на каждой итерации мы суммируем 2<sup>i-1</sup> чисел с другими 2<sup>i</sup>, а после O (log n) мы в итоге суммируем два n /2 битовых чисел, которые дают общее количество установленных битов.

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

При этом вы не можете считать произвольные длинные алгоритмы быстрее, чем Ω (n) , поскольку для определения его значения требуется хотя бы один раз прочитать каждый бит, если, конечно, вы ничего не знаете озаранее составленная структура числа.