Бинарная арифметика

Работая с двоичными числами необходимо знать, какие операции для них используются, как они выполняются и для чего это всё вообще нужно…
Начнём с простого, операции сложения, вычитания и умножения выглядят следующим образом:

С простыми арифметическими операциями, думаю, проблем не возникнет. Теперь перейдём к более сложным операциям:

  • Побитовая инверсия “~”: заменяет каждый бит операнда на противоположный;
  • Побитовое И “&”: эквивалент логический операции для пары битов, которые стоят на одинаковых позициях;
  • Побитовое ИЛИ “|”: эквивалент логического или для пары битов, стоящих на одинаковых позициях;
  • Побитовое исключающее ИЛИ (xor) “^”: (для простоты называют сложение по модулю 2) результат будет равен 1, если число складываемых битов нечетно и 0 если четно.
  • Побитовый сдвиг влево “<<”: сдвиг битов влево;
  • Побитовый сдвиг вправо “>>”: сдвиг битов вправо;

Теперь перейдём к самому полезному:

  • Чтобы обнулись самый крайний бит в числе, можно использовать формулу: x&(x-1)    Если данное выражение будет равно 0, то x является степенью двойки.
  • Чтобы установить крайний справа нулевой бит равным 1, а если такого нет, то все биты равными 1, то можно воспользоваться формулой: x|(x+1)
  • Чтобы превратить все завершающие единичные биты в нули, а если таких нет, то вернуть исходное значение: x&(x+1)
  • Чтобы превратить все завершающие нулевые биты в единичные, а если таких нет, то вернуть исходное значение: x|(x-1)

Вычисление следующего большего числа с тем же количеством единичных битов:

        private static uint Snoob(uint x)
        {
            var buf = x & (x - 1);
            uint smallest = x & (x ^ buf);
            uint ripple = x + smallest;
            uint ones = x ^ ripple;
            ones = (ones >> 2) / smallest;
           return ripple | ones;
        }
Работа с битами чисел может помочь в некоторых случаях, когда необходимо ускорить узкие места программы… Приятного программирования…

Добавить комментарий