Объясните логику алгоритма подсчета битнов Кернигана

Этот вопрос непосредственно следует после прочтения алгоритма подсчета битов (Брайан Керниган) в целочисленной временной сложности. Код Java, о котором идет речь,

int count_set_bits(int n) {
  int count = 0;
    while(n != 0) {
      n &= (n-1);
      count++;
    }
 }

Я хочу понять, что здесь делает n &= (n-1)? Я видел аналогичную конструкцию в другом отличном алгоритме для определения того, является ли число силой 2, например:

if(n & (n-1) == 0) {
    System.out.println("The number is a power of 2");
}

Ответы

Ответ 1

Выполнение кода в отладчике помогло мне.

Если вы начинаете с

n = 1010101 & n-1=1010100 => 1010100
n = 1010100 & n-1=1010011 => 1010000
n = 1010000 & n-1=1001111 => 1000000
n = 1000000 & n-1=0111111 => 0000000

Таким образом, это повторяется 4 раза. Каждая итерация уменьшает значение таким образом, что младший значащий бит, установленный в 1, исчезает.

Дескрипция одним переводом младшего бита и каждого бита до первого. например если у вас 1000... 0000 -1 = 0111.... 1111 не имеет значения, сколько бит ему нужно перевернуть, и оно останавливается, оставляя ненужные другие биты. Когда вы и это с n, самый младший бит установлен и только младший бит становится 0

Ответ 2

Вычитание 1 из числа переключает все биты (справа налево) до самого правого установленного бита (в том числе самого младшего установленного бита). Поэтому, если мы вычтем число на 1 и побитовое и с самим собой (n & (n-1)), мы отменим бит с минимальным множеством. Таким образом, мы можем отключить 1s один за другим справа налево в цикле.

Число повторений цикла равно числу установленных биты.

Источник: Алгоритм Брайана Кернигана