Использование побитовых операторов для упаковки нескольких значений в один int

Малоуровневая манипуляция низкого уровня никогда не была моей сильной стороной. Я позабочусь о помощи в понимании следующего варианта использования побитовых операторов. Обратите внимание...

int age, gender, height, packed_info;

. . .   // Assign values 

// Pack as AAAAAAA G HHHHHHH using shifts and "or"
packed_info = (age << 8) | (gender << 7) | height;

// Unpack with shifts and masking using "and"
height = packed_info & 0x7F;   // This constant is binary ...01111111
gender = (packed_info >> 7) & 1;
age    = (packed_info >> 8);

Я не уверен, что этот код выполняет и как? Зачем использовать магический номер 0x7F? Как выполняется упаковка и распаковка?

Источник

Ответ 1

Как говорится в комментарии, мы собираем возраст, пол и высоту в 15 бит формата:

AAAAAAAGHHHHHHH

Начнем с этой части:

(age << 8)

Для начала возраст имеет такой формат:

age           = 00000000AAAAAAA

где каждый A может быть 0 или 1.

<< 8 перемещает биты 8 мест влево и заполняет пробелы нулями. Итак, вы получаете:

(age << 8)    = AAAAAAA00000000

Аналогично:

gender        = 00000000000000G
(gender << 7) = 0000000G0000000
height        = 00000000HHHHHHH

Теперь мы хотим объединить их в одну переменную. Оператор | работает, просматривая каждый бит и возвращая 1, если бит равен 1 в любом из входов. Итак:

0011 | 0101 = 0111

Если бит равен 0 на одном входе, вы получаете бит от другого ввода. Посмотрев (age << 8), (gender << 7) и height, вы увидите, что если бит равен 1 для одного из них, то 0 для остальных. Итак:

packed_info = (age << 8) | (gender << 7) | height = AAAAAAAGHHHHHHH

Теперь мы хотим распаковать бит. Пусть начнется с высоты. Мы хотим получить последние 7 бит и проигнорировать первые 8. Для этого мы используем оператор &, который возвращает 1, только если оба входных бита равны 1. Итак:

0011 & 0101 = 0001

Итак:

packed_info          = AAAAAAAGHHHHHHH
0x7F                 = 000000001111111
(packed_info & 0x7F) = 00000000HHHHHHH = height

Чтобы получить возраст, мы можем просто нажать все 8 мест вправо, и мы останемся с 0000000AAAAAAAA. Итак age = (packed_info >> 8).

Наконец, чтобы получить пол, мы выталкиваем все 7 мест вправо, чтобы избавиться от высоты. Мы заботимся только о последнем бите:

packed_info            = AAAAAAAGHHHHHHH
(packed_info >> 7)     = 0000000AAAAAAAG
1                      = 000000000000001
(packed_info >> 7) & 1 = 00000000000000G

Ответ 2

Это может быть довольно длинным уроком в манипуляции бит, но сначала позвольте мне также указать статью о маскировании бит в Википедии.

packed_info = (age << 8) | (gender << 7) | height;

Возьмите возраст и переместите его на 8 бит, затем возьмите пол и переместите его на 7 бит, а высота займет последние бит.

age    = 0b101
gender = 0b1
height = 0b1100
packed_info = 0b10100000000
            | 0b00010000000
            | 0b00000001100
/* which is */
packed_info = 0b10110001100

Распаковка делает обратное, но использует маски, такие как 0x7F (что равно 0b 01111111), чтобы обрезать другие значения в поле.

gender = (packed_info >> 7) & 1;

Будет работать как...

gender = 0b1011 /* shifted 7 here but still has age on the other side */
       & 0b0001
/* which is */
gender = 0b1

Обратите внимание, что ANDing что-либо в 1 является таким же, как "сохранение" этого бита, а ANDing с 0 совпадает с "игнорированием" этого бита.

Ответ 3

Если вы собираетесь хранить дату как число, возможно, вы достигнете ее, умножив год на 10000, месяц на 100 и добавив день. Дата, например, 2 июля 2011 года, будет закодирована как номер 20110702:

    year * 10000 + month * 100 + day -> yyyymmdd
    2011 * 10000 + 7 * 100 + 2 -> 20110702

Можно сказать, что мы закодировали дату в маске yyyymmdd. Мы могли бы описать эту операцию как

Сдвиньте 4 года вперед влево,
сдвиньте позиции месяца 2 влево и
оставить день как есть.
Затем объедините три значения вместе.

Это то же самое, что происходит с кодировкой возраста, пола и высоты, только то, что автор думает в двоичном формате.

См. диапазоны, которые могут иметь эти значения:

    age: 0 to 127 years
    gender: M or F
    height: 0 to 127 inches

Если мы переведем эти значения в двоичные, мы получим следующее:

    age: 0 to 1111111b (7 binary digits, or bits)
    gender: 0 or 1 (1 bit)
    height: 0 to 1111111b (7 bits also)

С учетом этого мы можем кодировать данные возраста и пола с помощью маски aaaaaaaghhhhhhh, только здесь мы говорим о двоичных цифрах, а не о десятичных цифрах.

Итак,

Сдвиньте возраст 8 бит влево,
сдвиньте пол 7 бит влево и
оставить высоту как есть.
Затем объедините все три значения вместе.

В двоичном выражении оператор Shift-Left (< <) перемещает значение n позиций влево. Оператор "Or" ( "|" на многих языках) объединяет значения вместе. Поэтому:

    (age << 8) | (gender << 7) | height

Теперь, как "декодировать" эти значения?

Это проще в двоичном, чем в десятичном:

Вы "маскируете" высоту,
сдвиньте пол 7 бит вправо и замаскируйте его также, и, наконец,
сдвиньте возраст на 8 бит вправо.

Оператор Shift-Right ( → ) перемещает значение n позиций вправо (любые цифры, сдвинутые "из" крайнего правого положения, теряются). Бинарный оператор "И" ( "&" на многих языках) маскирует биты. Для этого ему нужна маска, указывающая, какие биты нужно сохранить и какие биты уничтожить (1 бит сохранен). Поэтому:

    height = value & 1111111b (preserve the 7 rightmost bits)
    gender = (value >> 1) & 1 (preserve just one bit)
    age = (value >> 8)

Так как 1111111b в шестнадцатеричном формате составляет 0x7f на большинстве языков, это причина этого магического числа. Вы будете иметь тот же эффект, используя 127 (что равно 1111111b в десятичной форме).

Ответ 4

Левый оператор сдвига означает "умножить на два, это много раз". В двоичном выражении умножение числа на два совпадает с добавлением нуля в правую сторону.

Оператор правого сдвига - это обратный оператор левого сдвига.

Оператор трубы - "или", что означает наложение двух двоичных чисел друг на друга и где в каждом из них есть 1, результат в этом столбце равен 1.

Итак, давайте извлеките операцию для packet_info:

// Create age, shifted left 8 times:
//     AAAAAAA00000000
age_shifted = age << 8;

// Create gender, shifted left 7 times:
//     0000000G0000000
gender_shifted = gender << 7;

// "Or" them all together:
//     AAAAAAA00000000
//     0000000G0000000
//     00000000HHHHHHH
//     ---------------
//     AAAAAAAGHHHHHHH
packed_info = age_shifted | gender_shifted | height;

И распаковка - это обратное.

// Grab the lowest 7 bits:
//     AAAAAAAGHHHHHHH &
//     000000001111111 =
//     00000000HHHHHHH
height = packed_info & 0x7F;

// right shift the 'height' bits into the bit bucket, and grab the lowest 1 bit:
//     AAAAAAAGHHHHHHH 
//   >> 7 
//     0000000AAAAAAAG &
//     000000000000001 =
//     00000000000000G
gender = (packed_info >> 7) & 1;

// right shift the 'height' and 'gender' bits into the bit bucket, and grab the result:
//     AAAAAAAGHHHHHHH 
//   >> 8
//     00000000AAAAAAA
age    = (packed_info >> 8);

Ответ 5

Более конденсированный ответ:

AAAAAAA G HHHHHHH

Упаковка:

packed = age << 8 | gender << 7 | height

В качестве альтернативы вы можете просто суммировать компоненты, если, например, при использовании в агрегатной функции MySQL SUM

packed = age << 8 + gender << 7 + height

Распаковка:

age = packed >> 8 // no mask required
gender = packed >> 7 & ((1 << 1) - 1) // applying mask (for gender it is just 1)
height = packed & ((1 << 7) - 1) // applying mask

Другой (более длинный) пример:

Скажем, у вас есть IP-адрес, который вы хотите упаковать, однако это вымышленный IP-адрес, например 132.513.151.319. Обратите внимание, что некоторые компоненты больше 256, которые требуют больше 8 бит, в отличие от реальных ip-адресов.

Сначала нам нужно выяснить, какое смещение нам нужно использовать, чтобы иметь возможность хранить максимальное число. Скажем, с нашими вымышленными IP-адресами ни один компонент не может быть больше, чем 999, что означает, что нам нужно 10 бит хранения на один компонент (позволяет номера до 1014).

packed = (comp1 << 0 * 10) | (comp1 << 1 * 10) | (comp1 << 2 * 10) | (comp1 << 3 * 10)

Что дает dec 342682502276 или bin 100111111001001011110000000010010000100

Теперь давайте распакуем значение

comp1 = (packed >> 0 * 10) & ((1 << 10) - 1) // 132
comp2 = (packed >> 1 * 10) & ((1 << 10) - 1) // 513
comp3 = (packed >> 2 * 10) & ((1 << 10) - 1) // 151
comp4 = (packed >> 3 * 10) & ((1 << 10) - 1) // 319

Где (1 << 10) - 1 - двоичная маска, которую мы используем, чтобы скрыть бит слева от 10 самых правых наиболее интересующих нас битов.

Тот же пример с использованием MySQL-запроса

SELECT

(@offset := 10) AS `No of bits required for each component`,
(@packed := (132 << 0 * @offset) | 
            (513 << 1 * @offset) | 
            (151 << 2 * @offset) | 
            (319 << 3 * @offset)) AS `Packed value (132.513.151.319)`,

BIN(@packed) AS `Packed value (bin)`,

(@packed >> 0 * @offset) & ((1 << @offset) - 1) `Component 1`,
(@packed >> 1 * @offset) & ((1 << @offset) - 1) `Component 2`,
(@packed >> 2 * @offset) & ((1 << @offset) - 1) `Component 3`,
(@packed >> 3 * @offset) & ((1 << @offset) - 1) `Component 4`;

Ответ 6

Вы можете видеть выражение x & mask как операцию, которая удаляет из x биты, которые не присутствуют (т.е. имеют значение 0) в mask. Это означает, что packed_info & 0x7F удаляет из packed_info все биты, которые превышают седьмой бит.

Пример: если packed_info 1110010100101010 в двоичном формате, то packed_info & 0x7F будет

1110010100101010
0000000001111111
----------------
0000000000101010

Итак, в height мы получаем младшие 7 бит packed_info.

Затем мы переместим целое packed_info на 7, таким образом мы удалим информацию, которую мы уже зачитали. Таким образом, мы получаем (для значения из предыдущего примера) 111001010 Пол сохраняется в следующем бите, поэтому с тем же трюком: & 1 мы извлекаем только этот бит из информации. Остальная часть информации содержится в смещении 8.

Не слишком сложна упаковка: вы берете age, сдвигаете его на 8 бит (чтобы вы получили 1110010100000000 от 11100101), сдвиньте gender на 7 (так что вы получите 00000000), и принять высоту (при условии, что она будет соответствовать более низким 7 бит). Затем вы объединяете их вместе:

1110010100000000
0000000000000000
0000000000101010
----------------
1110010100101010

Ответ 7

То же требование, с которым я сталкивался много раз. Это очень легко с помощью побитового оператора И. Просто квалифицируйте свои ценности с увеличением полномочий двух (2). Чтобы сохранить несколько значений, добавьте их относительное число (мощность 2) и получите SUM. Этот СУММ будет консолидировать выбранные вами значения. КАК?

Просто побитовое И с каждым значением, и оно даст нуль (0) для значений, которые не были выбраны, и ненулевое значение для которых выбрано.

Вот объяснение:

1) Значения (YES, NO, MAYBE)

2) Присвоение мощности двух (2)

YES   =    2^0    =    1    =    00000001
NO    =    2^1    =    2    = 00000010
MAYBE =    2^2    =    4    = 00000100

3) Я выбираю YES и MAYBE, следовательно SUM:

SUM    =    1    +    4    =    5

SUM    =    00000001    +    00000100    =    00000101

Это значение сохранит как YES, так и MAYBE. КАК?

1    &    5    =    1    ( non zero )

2    &    5    =    0    ( zero )

4    &    5    =    4    ( non zero )

Следовательно, SUM состоит из

1    =    2^0    =    YES
4    =    2^2    =    MAYBE.

Для более подробного объяснения и реализации посетите мой blog