Нужна помощь в понимании метода "getbits ()" в Главе 2 K & R C

Question

В главе 2, разделе о побитовых операторах (раздел 2.9), у меня возникают проблемы с пониманием того, как работает один из примеров методов.

Вот метод, предоставленный:

unsigned int getbits(unsigned int x, int p, int n) {
    return (x >> (p + 1 - n)) & ~(~0 << n);
}

Идея состоит в том, что для данного числа x он вернет n битов, начиная с позиции p , считая справа (с самый дальний правый бит - позиция 0). Учитывая следующий main() метод:

int main(void) {
    int x = 0xF994, p = 4, n = 3;
    int z = getbits(x, p, n);
    printf("getbits(%u (%x), %d, %d) = %u (%X)\n", x, x, p, n, z, z);

    return 0;
}

Вывод:

getbits(63892 (f994), 4, 3) = 5 (5)

Я получаю части этого, но у меня проблемы с «большой картиной», в основном из-за битов (без каламбура), которые я не понимаю.

Часть, с которой у меня возникли проблемы, это часть дополнения: ~(~0 << n). Я думаю, что я получил первую часть, имеющую дело с x ; С этой частью (а затем и с маской) я борюсь - и как все это объединяется, чтобы на самом деле получить эти биты. (Я проверял, что он делает, и с кодом, и проверяя мои результаты, используя calc.exe - слава Богу, у него есть двоичное представление!)

Любая помощь?

Answer 1

Давайте используем 16 бит для нашего примера. В этом случае ~ 0 равно

1111111111111111

Когда мы сдвигаем влево эти n биты (3 в вашем случае), мы получаем:

1111111111111000

потому что 1 s слева отбрасываются, а 0 s вводятся справа. Затем повторное дополнение дает:

0000000000000111

так что это просто умный способ получить n 1-бит в наименее значимой части числа.

Описанный вами «бит x» сместил заданное число (f994) достаточно далеко, так что младшие 3 бита - это те, которые вам нужны. В этом примере запрашиваемые биты заключены в '.' символы.

ff94             11111111100.101.00  # original number
>> p+1-n     [2] 0011111111100.101.  # shift desired bits to right
& ~(~0 << n) [7] 0000000000000.101.  # clear all the other (left) bits

И вот у вас есть свои биты. Та да !!

Answer 2

Я бы сказал, что лучше всего решить проблему вручную, чтобы вы поняли, как она работает.

Вот что я сделал, используя 8-битное беззнаковое целое.

1. Наше число 75, мы хотим, чтобы 4 бита начинались с позиции 6. вызов для функции будет getbits (75,6,4);

2. 75 в двоичном виде - 0100 1011

3. Итак, мы создаем маску длиной 4 бита, начиная с бита самого низкого порядка, это делается как таковое.

~ 0 = 1111 1111
<< 4 = 1111 0000 <br> ~ = 0000 1111

Хорошо, мы получили нашу маску.

4. Теперь мы помещаем нужные биты из числа в биты младшего разряда так, мы сдвигаем двоичный код 75 на 6 + 1-4 = 3.

0100 1011 >> 3 0000 1001

Теперь у нас есть маска правильного числа битов в младшем порядке и битов, которые мы хотим получить от исходного числа в младшем порядке.

4. поэтому мы и они
   

  0000 1001 <br />
& 0000 1111
============

  0000 1001

поэтому ответ десятичный 9.

Примечание: просто клев высшего порядка - это все нули, в этом случае маскировка избыточна, но это может быть что угодно, в зависимости от значения числа, с которого мы начали.

Answer 3

~(~0 << n) создает маску с включенными n крайними правыми битами.

0
   0000000000000000
~0
   1111111111111111
~0 << 4
   1111111111110000
~(~0 << 4)
   0000000000001111

И результат с чем-то еще вернет то, что находится в этих n битах.

Редактировать: я хотел бы отметить калькулятор этого программиста, который я использовал навсегда: AnalogX PCalc .

Answer 4

Никто еще не упомянул об этом, но в ANSI C ~0 << n вызывает неопределенное поведение.

Это потому, что ~0 - отрицательное число, а отрицательные числа со сдвигом влево не определены.

Ссылка: C11 6.5.7 / 4 (более ранние версии имели похожий текст)

Результат E1 << E2 равен E1 смещенным влево E2 битовым позициям; освобожденные биты заполнены нулями. [...] Если у E1 есть подпись тип и неотрицательное значение, и E1 × 2E2 представимо в типе результата, то есть это результирующее значение; в противном случае поведение не определено.

В K & R C этот код основывался бы на конкретном классе систем, на которых разработал K & R, наивно сдвигая 1 битов влево при выполнении сдвига влево числа со знаком (и этот код также опирается на представление дополнения 2) ), но некоторые другие системы не имеют этих свойств, поэтому процесс стандартизации C не определил это поведение.

Так что этот пример действительно интересен только как историческое любопытство, его не следует использовать ни в каком реальном коде с 1989 года (если не раньше).

Answer 5

Используя пример: int x = 0xF994, p = 4, n = 3; int z = getbits (x, p, n);

и сосредоточиться на этом наборе операций ~ (~ 0 << n) </p>

для любого набора битов (10010011 и т. Д.), Который вы хотите создать "маску", которая извлекает только те биты, которые вы хотите увидеть. Итак, 10010011 или 0x03, я заинтересован в xxxxx011. Какая маска будет извлекать этот набор? 00000111 Теперь я хочу быть независимым от размера int, я позволю машине выполнять работу, то есть начать с 0 для байтовой машины, это 0x00 для текстовой машины, это 0x0000 и т.д.

Теперь примените «не» (~ 0) и получите 11111111
сдвиньте вправо (<<) на n и получите 11111000 <br> а "не" то и получится 00000111

поэтому 10010011 и 00000111 = 00000011
Вы помните, как работают логические операции?

Answer 6

В ANSI C ~0 >> n вызывает неопределенное поведение

// сообщение о сдвиге влево, вызывающем проблему, неверно.

беззнаковый символ м, л;

м = ~ 0 >> 4; производит 255 и равно ~ 0, но

м = ~ 0; l = m >> 4; выдает правильное значение 15, такое же как:

м = 255 >> 4;

нет проблем с отрицательным смещением влево ~0 << вообще