Базы данныхИнтернетКомпьютерыОперационные системыПрограммированиеСетиСвязьРазное
Поиск по сайту:
Подпишись на рассылку:

Назад в раздел

Трюки - манипуляции c битами.

Трюки - манипуляции c битами Трюки - манипуляции c битами

Автор: Аркадий Белоусов, письмо от 19 сентября 1999 года в эхоконференции fido7.RU.ALGORITHMS.

Примеры даны для языка Си. Если Вам требуется перевести трюки на другой язык, то запомните, что в языке Си:
^ - Исключающее ИЛИ, & - И, | - ИЛИ, ~ - НЕ.

Подсчёт количества ненулевых бит в числе v за log2(v) проходов

На примере 8-битного числа:

v = (v & 0x55) + ((v >> 1) & 0x55); v = (v & 0x33) + ((v >> 2) & 0x33); return (v & 0x0f) + ((v >> 4) & 0x0f);

Число разбивается на группы бит одной длины (сперва по одному биту). Затем значения соседних пар одновременно складываются и сохраняются в новых группах в два раза большей длины до тех пор, пока не будут сложены половинки числа.

Поскольку длина суммы двух чисел равна длине большего числа с битом для переноса, поэтому для каждой группы в маске групп достаточно иметь единиц не больше номера шага (то есть 1+log2 от длины группы). Hапример, для подсчёта единичных бит в 32-битном числе (с оптимизацией):

#define g21 0x55555555ul // = 0101_0101_0101_0101_0101_0101_0101_0101 #define g22 0x33333333ul // = 0011_0011_0011_0011_0011_0011_0011_0011 #define g23 0x0f0f0f0ful // = 0000_1111_0000_1111_0000_1111_0000_1111 v = (v & g21) + ((v >> 1) & g21); v = (v & g22) + ((v >> 2) & g22); v = (v + (v >> 4)) & g23; return (v + (v >> 8) + (v >> 16) + (v >> 24)) & 0x3f; Для сокращения количества шагов можно суммировать тройки и т.д.: #define g31 0x49249249ul // = 0100_1001_0010_0100_1001_0010_0100_1001 #define g32 0x381c0e07ul // = 0011_1000_0001_1100_0000_1110_0000_0111 v = (v & g31) + ((v >> 1) & g31) + ((v >> 2) & g31); v = ((v + (v >> 3)) & g32) + ((v >> 6) & g32); return (v + (v >> 9) + (v >> 18) + (v >> 27)) & 0x3f; Сбросить младший ненулевой бит/проверить, является ли число степенью двойки: (n - 1) & n // (для модификации n: n &= n - 1) if((n - 1) & n == 0) // ...степень двойки... Выделить младший единичный бит: ((n - 1) ^ n) & n ((n - 1) & n) ^ n ~(n - 1) & n // (более оптимальный вариант) Поменять местами значение двух переменных, не используя третью: a ^= b ^= a ^= b; Заменить одно значение на другое в переменной, которая может принимать только эти два значения: v = (val1 + val2) - v; v ^= val1 ^ val2; // (более оптимальный вариант) Подсчитать номер младшего единичного бита (n должен быть ненулевым):

Привет для 32-битного числа.

k = 0; if((n & 0xFFFF) == 0) k = 16, n >>= 16; if((n & 0x00FF) == 0) k += 8, n >>= 8; if((n & 0x000F) == 0) k += 4, n >>= 4; if((n & 0x0003) == 0) k += 2, n >>= 2; if((n & 0x0001) == 0) k += 1; Подсчитать номер старшего единичного бита (если n=0, то k=32):

Привет для 32-битного числа.

k = 0; if(n & 0xFFFF0000) k = 16, n >>= 16; if(n & 0x0000FF00) k += 8, n >>= 8; if(n & 0x000000F0) k += 4, n >>= 4; if(n & 0x0000000С) k += 2, n >>= 2; if(n & 0x00000002) k += 1;

Автор: Аркадий Белоусов (Arkady V.Belousov), ark@belous.munic.msk.su.

Перевод в HTML - Акжан Абдулин, akzhan@info.khv.ru, 6 октября 1999 года.



  • Главная
  • Новости
  • Новинки
  • Скрипты
  • Форум
  • Ссылки
  • О сайте




  • Emanual.ru – это сайт, посвящённый всем значимым событиям в IT-индустрии: новейшие разработки, уникальные методы и горячие новости! Тонны информации, полезной как для обычных пользователей, так и для самых продвинутых программистов! Интересные обсуждения на актуальные темы и огромная аудитория, которая может быть интересна широкому кругу рекламодателей. У нас вы узнаете всё о компьютерах, базах данных, операционных системах, сетях, инфраструктурах, связях и программированию на популярных языках!
     Copyright © 2001-2024
    Реклама на сайте