Многие знают, что происходит при выполнении присваивания "n &= (n - 1);" просто потому, что это весьма распространенный шаблон, и для чего может понадобиться выполнение его в цикле, пока n не станет нулем.
Интересно другое: четкое математическое (и/или алгоритмическое) объяснение, почему это работает именно так, строгое доказательство.
Update:
Чтобы разобраться в вопросе надо понять, что является корнем недопонимания.
Для людей, не часто имеющих дело с двоичной системой, обычно не совсем очевидна суть трансформации внутреннего двоичного представления числа при выполнении арифметической операции в десятичной нотации. Кажется, что если вычесть единицу, то расположение битов после операции будет иметь мало общего с тем, что было до вычитания. И дальнейшее выполнение "and" вообще не имеет смысла.
С точки зрения битового представления любого числа, есть только два случая:
1. Если число нечетное, на конце будет единица: "xx...xx1". Вычитание из такого числа даст: "хх...хх0". Поэтому "(xx...xx1) & (xx...xx0)" даст "(xx...xx0)". Фактически, мы убрали младший бит.
2. Если число четное, на конце будет ноль (или несколько нулей): "xx...xx100...00". Видно, что вычитание единицы из такого числа однозначно не изменит разряды "xx...xx", стоящие слева после первой единицы. Более того, результат вычитания единицы однозначно предсказуем: "xx...xx011...11". Теперь точно видно, что будет после операции "and": ("xx...xx100...00") & ("xx...xx011...11") даст ""xx...xx000...00". То есть мы убрали единицу из самого младшего ненулевого разряда.
Теперь ясно видно, что именно проиходит в присваивании "n &= (n - 1);". А именно, обнуление самого младшего ненулевого разряда.
Использование этого трюка в цикле, пока n не равно нулю, позволяет подсчитать количество ненулевых бит. На каждой итерации мы "выбиваем" ровно один бит, поэтому Число итераций будет равно количеству единиц в n.
среда, 21 апреля 2010 г.
Подписаться на:
Комментарии к сообщению (Atom)
Сообщения
Это проверка является ли число n степенью двойки?
ОтветитьУдалитькак написано тут http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/
ОтветитьУдалитьThe mystical line n &= (n – 1) simply sets the rightmost 1 bit in n to 0
11111111 255
11111110->254
11111110 254
11111101->252
11111100 252
11111011->248
11111000 248
11110111->240
11110000 240
11101111->224
11100000 224
11011111->192
11000000 192
10111111->128
10000000 128
01111111->0
sergeyerokhin: Хотелось бы иметь строгое объяснение в терминах двоичного сумматора и булевых функций.
ОтветитьУдалитьОбновил пост своим объяснением.
ОтветитьУдалитьА я только закончил строчить объяснение у себя:
ОтветитьУдалитьhttp://blog.zfilin.org.ua/2010/04/n-n-1_21.html
(очень много сил отнимает форматирование формул, нужно будет как-то прикрутить LaTeX)
Это не очень плохо, что я ссылаюсь на себя все-время? А-то я попробовал в каментах тэги sub применить, но оно не разрешает...
Елки-палки! Мы старшую часть байта одинаково обозначаем:
ОтветитьУдалитьxx...xx
Теперь вообще можно подумать, что я все "списал". =(
Все очень понятно и строго расписано.
ОтветитьУдалитьт.о. кол-во битовых единиц N в числе мы можем узнать за O(N), а можно за log(K), где K - разрядность числа
ОтветитьУдалитькак пример java.lang.Long.bitCount (тут же в общем-то и подсказка на источник):
public static int bitCount(long i) {
// HD, Figure 5-14
i = i - ((i >>> 1) & 0x5555555555555555L);
i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
i = i + (i >>> 8);
i = i + (i >>> 16);
i = i + (i >>> 32);
return (int)i & 0x7f;
}
разрядность long в java = 64 бита
ОтветитьУдалитьА я для этой задачи всегда использовал такую функцию
ОтветитьУдалитьint GetBitCount(dword 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 (int)x;
}
Спасибо! Не знал о таком варианте подсчета ненулевых битов.
ОтветитьУдалить