k & r проявляет путаницу с битовыми операциями

Question

Упражнение это: Напишите функцию setbits (x, p, n, y), которая возвращает x с n битами, которые начинаются с позиции p, равной крайним правым n битам y, оставляя остальные биты неизменными.

Моя попытка найти решение:

#include <stdio.h>

unsigned setbits(unsigned, int, int, unsigned);

int main(void)
{
    printf("%u\n", setbits(256, 4, 2, 255));
    return 0;
}

unsigned setbits(unsigned x, int p, int n, unsigned y)
{
    return (x >> (p + 1 - n)) | (1 << (n & y));
}

Возможно, это неправильно, но я на правильном пути? Если нет, что я делаю не так? Я не уверен, почему я не совсем понимаю, но я потратил около часа, пытаясь придумать это.

Спасибо.

Answer 1

Вот ваш алгоритм:

1. Если n равно 0, вернуть x.
2. Возьмите 1 и сдвиньте влево n раз, а затем вычтите 1. Назовите это mask.
3. Маска левого сдвига p раз вызывает это mask2.
4. And x с инверсией маски2. And у с маской и смещением влево p раз.
5. Or результаты этих двух операций и возвращаем это значение.

Answer 2

Я думаю, что ответом является слегка измененное приложение примера getbits из раздела 2.9.

Давайте разберем его следующим образом:

Let bitstring x be 1 0 1 1 0 0
Let bitstring y be 1 0 1 1 1 1

positions -------->5 4 3 2 1 0

Установка p = 4 and n =3 дает нам цепочку битов из x, которая равна 0 1 1. Он начинается в 4 и заканчивается в 2 и охватывает 3 элемента.

Мы хотим заменить 0 1 1 на 1 1 1 (последние три элемента цепочки бит y).

Давайте на время забудем о сдвиге влево / вправо и представим проблему следующим образом:

Нам нужно извлечь последние три цифры из строки битов y, которая равна 1 1 1

Разместите 1 1 1 непосредственно под позициями 4 3 and 2 цепочки битов x.

Заменить 0 1 1 на 1 1 1, оставляя остальные биты нетронутыми ...

Теперь давайте углубимся в детали ...

Мое первое утверждение было:

We need to grab the last three digits from bitstring y which is 1 1 1

Способ изолировать биты от цепочки битов состоит в том, чтобы сначала начать с цепочки битов, которая имеет все 0. Мы заканчиваем с 0 0 0 0 0 0.

0 обладают этим невероятным свойством, где побитовое «&» с другим числом дает нам все 0, а побитовое «|» с другим числом возвращает нам это другое число.

0 само по себе здесь бесполезно ... но оно говорит нам, что если мы '|' последние три цифры y с '0', в итоге мы получим 1 1 1. Остальные биты в y на самом деле нас здесь не интересуют, поэтому нам нужно найти способ обнулить эти числа, сохраняя при этом последние три цифры без изменений. По сути нам нужен номер 0 0 0 1 1 1.

Итак, давайте посмотрим на серию необходимых преобразований:

Start with  ->  0 0 0 0 0 0
apply ~0    ->  1 1 1 1 1 1
lshift by 3 ->  1 1 1 0 0 0 
apply ~     ->  0 0 0 1 1 1
& with y    ->  0 0 0 1 1 1 & 1 0 1 1 1 1 -> 0 0 0 1 1 1

И таким образом у нас есть последние три цифры, которые будут использоваться для целей настройки ...

Мое второе утверждение было:

Поместите 1 1 1 непосредственно в позиции 4 3 и 2 цепочки битов x.

Подсказку для этого можно найти в примере getbits в разделе 2.9. То, что мы знаем о позициях 4,3 и 2, можно узнать из значений p = 4 and n =3. p - это позиция, а n - длина набора битов. Оказывается, p+1-n дает нам смещение набора битов от самого правого бита. В этом конкретном примере p+1-n = 4 +1-3 = 2.

Итак ... если мы сделаем сдвиг влево на 2 строки 0 0 0 1 1 1, мы получим 0 1 1 1 0 0. Если вы поместите эту строку в x, вы заметите, что 1 1 1 совпадает с позициями 4 3 and 2 в x.

Мне кажется, я наконец-то кое-что получил ... последнее заявление, которое я сделал ...

Заменить 0 1 1 на 1 1 1, оставив остальные биты нетронутыми ...

Теперь рассмотрим наши строки:

x           ->   1 0 1 1 0 0
isolated y  ->   0 1 1 1 0 0

Выполнение побитового или с этими двумя значениями дает нам то, что нам нужно для этого случая:

1 1 1 1 0 0 

Но это не получится, если вместо 1 1 1 у нас будет 1 0 1 ... поэтому, если нам нужно еще немного покопаться, чтобы добраться до нашей "серебряной пули" ...

Давайте посмотрим на две вышеупомянутые строки еще раз ...

x -> bit by bit...1(stays) 0(changes) 1(changes) 1(changes) 0(stays) 0(stays)

Так что в идеале ... нам нужна цепочка битов 1 x x x 0 0, где x поменяется местами с 1. Вот прыжок интуиции, который поможет нам ..

Bitwise complement of isolated y -> 1 0 0 0 1 1
& this with x gives us           -> 1 0 0 0 0 0
| this with isolated y           -> 1 1 1 1 0 0 (TADA!)

Надеюсь, этот длинный пост поможет людям рационализировать и решить такие проблемы с маскировкой ...

Спасибо

Answer 3

Обратите внимание, что ~0 << i дает число с младшими значащими битами i, установленными на 0, а остальные биты установлены на 1. Точно так же ~(~0 << i) дает вам число с наименьшими значащими битами i, установленными на 1, а остальные 0.

Теперь, чтобы решить вашу проблему:

1. Во-первых, вам нужно число, в котором есть все биты, кроме битов n, которые начинаются с позиции p, установленной на биты x. Для этого вам понадобится маска, содержащая 1 во всех местах, кроме битов n, начинающихся в позиции p:
   1. в этой маске установлены самые верхние (самые значимые) биты, начиная с бита в позиции p+1.
   2. эта маска также имеет наименее значимые p+1-n биты.
2. Если у вас есть вышеуказанная маска, & этой маски с x даст вам номер, который вы хотели получить на шаге 1.
3. Теперь вам нужно число, для которого установлены младшие значащие n биты y, смещенные влево p+1-n биты.
   1. Вы можете легко создать маску, в которой установлены только наименее значимые n биты, и &, используя y для извлечения y наименее значимых n бит.
   2. Затем вы можете сдвинуть это число на p+1-n бит.
4. Наконец, вы можете поразрядно или (|) результаты шагов 2 и 3.2 получить свой номер.

Ясно, как грязь? : -)

(Вышеуказанный метод не должен зависеть от размера чисел, что я считаю важным.)

Редактировать : глядя на ваши усилия: n & y ничего не делает с n битами. Например, если n равно 8, вы хотите, чтобы последние 8 бит y, но n & y просто выберет 4-й бит y (8 в двоичном виде - 1000). Итак, вы знаете, что это не может быть правильно. Точно так же, сдвиг вправо x p+1-n раз дает число, для которого старшие значащие биты p+1-n установлены на ноль, а остальные биты состоят из старших значащих бит x. Это не то, что вы хотите.