Количество единичных битов

Рейтинг: 2Ответов: 2Опубликовано: 28.10.2014

Здравствуйте, такой вопрос.

Необходимо подсчитать количество единичных битов в числе типа 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++ очевидно, что при каждой итерации у нас гарантированно получается отсчитать единичный бит.

Подскажите, в чем суть, и извините за стену текста.

Ответы

▲ 7Принят

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

10101
10100 = 10101 & 10100
10000 = 10100 & 10011
0
▲ 1

"Собственно здесь не могу понять. Ну n = 5 или n = 0b101 и n-1 = 4 или n-1 = 0b100, то есть 101 и 100. Я не вижу цитирую "отличается от n тем, что вместо последнего единичного бита у него 0, а все последующие биты равны 1". Младший бит равен 0 у четверки, но следующий тоже 0 а не 1."

Данный пример не общий, поэтому возникли трудности. Когда вычитается единица из n, то последний единичный бит инвертируется. В этом примере 101 -> 100. И так как правее единичного бита больше нет битов, то больше ничего не инвертируется. Если же рассмотреть другой пример, например 1100, то n-1 будет 1011: 1100 -> 1011. Здесь уже видно, что все правые биты инвертируются. Соответственно если применим & к n и n-1, то каждую итерацию получаем новое число, которое имеет на один единичный бит меньше, так как все биты, начиная с последнего единичного бита у числа n инвертированы по отношению к числу n-1. Таким образом, подсчитываем общее количество единиц.