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. Маска левого сдвига р раз это называют mask2,
4. And х с инверсией маски2. And у с маской и левым сдвигом р раз.
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 дает нам цепочку битов из х, которая 0 1 1, Он начинается в 4 и заканчивается в 2 и охватывает 3 элемента.

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

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

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

Место 1 1 1 прямо под позициями 4 3 and 2 цепочки битов х.

замещать 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 из х.

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

Замените 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где х будут поменяны местами с 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). Итак, вы знаете, что это не может быть правильно. Точно так же, вправо xp+1-n раз дает вам число, которое имеет наиболее значимое p+1-n биты установлены в ноль, а остальные биты состоят из наиболее значимых битов x, Это не то, что вы хотите.