Здравствуйте, такой вопрос.
Необходимо подсчитать количество единичных битов в числе типа int (java). Одним из решений, например, есть метод (из статьи на одном сайте про побитовые операции):
public int bitCounter(int n) {
int counter = 0;
while (n != 0) {
counter += n & 1;
n = n >>> 1;
}
return counter;
}
Тут все понятно: проверяем младший бит побитовым и с 1 и после сдвигаем биты вправо с заполнением нулями, в итоге доходим до нуля и получаем количество 1 битов.
И вот в статье дальше идет еще более улучшенное решение, не могу его понять в одном месте:
public int bitCounter(int n) {
int count = 0;
while (n != 0) {
count++;
n = n & (n - 1);
}
return count;
}
Написано: "Для этого рассмотрим выражение число (n - 1). Это число, отличается от n тем, что вместо последнего единичного бита у него 0, а все последующие биты равны 1".
Собственно здесь не могу понять. Ну n = 5 или n = 0b101 и n-1 = 4 или n-1 = 0b100, то есть 101 и 100.
Я не вижу цитирую "отличается от n тем, что вместо последнего единичного бита у него 0, а все последующие биты равны 1". Младший бит равен 0 у четверки, но следующий тоже 0 а не 1.
Где-то я туплю, но я не понимаю, как n = n & (n - 1) работает. По выражению count++ очевидно, что при каждой итерации у нас гарантированно получается отсчитать единичный бит.
Подскажите, в чем суть, и извините за стену текста.