K & R Вопрос: Нужна помощь в понимании метода getbits() в главе 2

Как я уже упоминал ранее, я прохожу через K & R, и в целом все в порядке с этим. Тем не менее, в главе 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 - слава богу, он имеет двоичный вид!)

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

Ответ 1

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

1111111111111111

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

1111111111111000

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

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

И у вас есть свои бит. Ta da!!

Ответ 2

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

Вот что я сделал с использованием 8-битного беззнакового int.

Наш номер - 75, мы хотим, чтобы 4 бита начинались с позиции 6. вызов функции будет getbits (75,6,4);
75 в двоичном формате - 0100 1011
Итак, мы создаем маску длиной 4 бита, начиная с бит младшего порядка, это делается как таковое.

~ 0 = 1111 1111
< 4 = 1111 0000
~ = 0000 1111

Хорошо, у нас есть наша маска.

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

0100 1011 → 3 0000 1001

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

поэтому мы и их

  0000 1001 

& 0000 1111
============

  0000 1001

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

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

Ответ 3

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

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

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

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

Ответ 4

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

и сосредоточив внимание на этом наборе операций ~ (~ 0 < n)

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

Теперь примените "не" (~ 0) и получите 11111111
сдвиг вправо (<) на n и получить 11111000
и "не", и получите 00000111

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

Ответ 5

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

Это связано с тем, что ~0 - отрицательное число, а отрицательные числа слева - undefined.

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

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

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

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