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

Question

Упражнение: Напишите набор функций (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. Если п 0, возвращение х.
2. Возьмите 1 и сдвиньте его влево, а затем вычтите 1. Назовите это mask.
3. Левая сменная маска p раз вызывает это mask2.
4. And x с инверсией mask2. And y с маской и левым сдвигом p раз.
5. Or результаты этих двух операций и вернуть это значение.

Answer 2

Обратите внимание, что ~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. Теперь вы хотите номер, который имеет наименее значащих битов ny набора, сдвинутый левый p+1-n бит.
   1. Вы можете легко сделать маску, которая имеет только младшие n установлены биты, и & его y извлечь y «s значащих 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. Это не то, что вы хотите.

Answer 3

Я думаю, что ответ является слегка измененным применением примера 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 (последние три элемента bitstring 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 

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

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

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) 

Так ideally..we нужно битовая 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!) 

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

Благодаря