*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 21 апреля 2010 г.

Смесь двоичной и десятичной арифметики

Многие знают, что происходит при выполнении присваивания "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.

11 комментариев:

  1. Это проверка является ли число n степенью двойки?

    ОтветитьУдалить
  2. как написано тут 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

    ОтветитьУдалить
  3. sergeyerokhin: Хотелось бы иметь строгое объяснение в терминах двоичного сумматора и булевых функций.

    ОтветитьУдалить
  4. Обновил пост своим объяснением.

    ОтветитьУдалить
  5. А я только закончил строчить объяснение у себя:
    http://blog.zfilin.org.ua/2010/04/n-n-1_21.html

    (очень много сил отнимает форматирование формул, нужно будет как-то прикрутить LaTeX)

    Это не очень плохо, что я ссылаюсь на себя все-время? А-то я попробовал в каментах тэги sub применить, но оно не разрешает...

    ОтветитьУдалить
  6. Елки-палки! Мы старшую часть байта одинаково обозначаем:
    xx...xx

    Теперь вообще можно подумать, что я все "списал". =(

    ОтветитьУдалить
  7. Все очень понятно и строго расписано.

    ОтветитьУдалить
  8. т.о. кол-во битовых единиц 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;
    }

    ОтветитьУдалить
  9. А я для этой задачи всегда использовал такую функцию

    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;
    }

    ОтветитьУдалить
  10. Спасибо! Не знал о таком варианте подсчета ненулевых битов.

    ОтветитьУдалить