Функция инвертирования бит в упражнении K&R 2-7

Упражнение 2-7 из Язык программирования C:

Напишите функцию invert(x,p,n), которая возвращает x с битами n, которые начинаются с позиции p, инвертированными (т. Е. 1 изменен на 0 и наоборот), оставив остальные без изменений.

Я понял вопрос так: у меня 182, что 101(101)10 в двоичном формате, часть в скобках должна быть инвертирована без изменения остальных. Возвращаемое значение должно быть 10101010, то есть 170 в десятичной системе.

Вот моя попытка:

#include <stdio.h>

unsigned int getbits(unsigned int bitfield, int pos, int num);
unsigned int invert(unsigned int bitfield, int pos, int num);

int main(void)
{
    printf("%d\n", invert(182, 4, 3));
    return 0;
}

/* getbits: get num bits from position pos */
unsigned int getbits(unsigned int bitfield, int pos, int num)
{
    return (bitfield >> (pos+1-n)) & ~(~0 << num);
}

/* invert: flip pos-num bits in bitfield */
unsigned int invert(unsigned int bitfield, int pos, int num)
{
    unsigned int mask;
    unsigned int bits = getbits(bitfield,pos,num);

    mask = (bits << (num-1)) | ((~bits << (pos+1)) >> num);

    return bitfield ^ mask;
}

Это кажется правильным (мне), но invert(182, 4, 3) выводит 536870730. getbits() работает нормально (прям из книги). Я записал, что происходит в выражении, которое я присвоил y:

(00000101 << 2) | ((~00000101 << 5) >> 3)    -- 000000101 is the part being flipped: 101(101)10
       00010100 | ((11111010 << 5) >> 3)
       00010100 | (01000000 >> 3)
       00010100 | 00001000
= 00011100

  10110110 (182)
^ 00011100
----------
= 10101010 (170)

Должно быть правильно, но это не так. Я выяснил, что здесь что-то не так: ((~xpn << (p+1)) >> n). Не понимаю как.

Кроме того, я понятия не имею, насколько общий этот код. Моя первоочередная задача - заставить это дело работать. Помощь в этом вопросе тоже приветствуется.


c bit-manipulation kernighan-and-ritchie
person sdf89    schedule 01.04.2013    source источник
comment
Не давайте переменным бессмысленных имен, таких как x, p, n, это действительно плохая идея.   -  person Lundin    schedule 01.04.2013
comment
@Lundin K&R назвал их так, я тоже. Хотя за этим могут быть причины форматирования. Я буду иметь это в виду.   -  person sdf89    schedule 01.04.2013
comment
Да, я понимаю, что действительно плохая идея пришла от K&R. Имейте в виду, что из этой книги нельзя научиться хорошей практике программирования. Из него можно только изучить синтаксис для версии языка C, которая устарела уже 14 лет.   -  person Lundin    schedule 01.04.2013
comment
@Lundin, эти имена переменных в порядке. K&R прав. По определению. Или посмотрите руководство по стилю ядра Linux C.   -  person vonbrand    schedule 01.04.2013
comment
@vonbrand Эээ, нет, извини, но в современном программировании нет такой вещи, как правильная по определению, потому что так сказал какой-то гуру в 80-х. Вдобавок ожидается, что программисты будут использовать собственный мозг. Если вы думаете, что x - отличное имя переменной, с использованием вашего мозга или без него, пусть будет так - дальнейшее обсуждение после такого вывода бессмысленно. Что касается стиля кодирования ядра Linux, то это довольно неформальный документ, в котором отсутствует достаточное обоснование или источники для сформулированных расплывчатых правил. Это, конечно, не какой-то канон C. Если вам нужен профессиональный стандарт кодирования, посмотрите MISRA-C или CERT-C.   -  person Lundin    schedule 02.04.2013

Ответы (5)


arrow_upward
4
arrow_downward

((1u<<n)-1) - это битовая маска с n битами «1» в правой части. <<p сдвигает этот блок из единиц p влево. (вы должны использовать (p-n) вместо p, если хотите считать слева).

return val  ^ (((1u<<n)-1) <<p) ;

По-прежнему существует проблема, когда p больше, чем размер слова (смещение больше, чем размер слова, не определено), но это должна быть ответственность вызывающего ;-)

Для примера 101(101)10 с p = 2 и n = 3:

1u<<n               := 1000
((1u<<n)-1)         := 0111
(((1u<<n)-1) <<p) := 011100
original val    := 10110110
val ^ mask      := 10101010
person wildplasser    schedule 01.04.2013
comment
Для чего нужна первая строка? Условие выполняется и для 0 - person SomeWittyUsername; 01.04.2013
comment
Это не нужно. (Я боялся, что маска превратится в все единицы, но (1<<0)-1 все нули. - person wildplasser; 01.04.2013
comment
Кажется, тоже не дает правильного ответа. Теперь я пояснил, как я понял упражнение в моем вопросе. Конечно, я мог это неправильно понять. - person sdf89; 01.04.2013
comment
Это counting from the right часть. В вашем примере 101(101)10 я предположил, что p = 2 и n = 3. - person wildplasser; 01.04.2013
comment
@wildplasser Я только что понял, что правильно посчитал p справа, но n слева. - person sdf89; 01.04.2013
comment
Я всегда считаю справа, потому что это не зависит от размера слова. wrt p: вы могли выразить свой block_to_be_inverted как bitpostions: = {2,3,4}; или от 2 до 5; или с 4 до 1; но это сбивает с толку (а последнее может даже привести к возникновению отрицательных значений). - person wildplasser; 01.04.2013

arrow_upward
1
arrow_downward

Думаю, в одну из смен у вас возникли отдельные проблемы (это всего лишь догадка, я не совсем уверен). Тем не менее, я бы все упростил (я предполагаю, что позиция индекса p начинается с младшего разряда, т.е. p = 0 - это младший бит):

unsigned int getbits(unsigned int x, int p, int n) {
  unsigned int ones = ~(unsigned int)0;
  return x ^ (ones << p) ^ (ones << (p+n));
}

изменить: если вам нужно, чтобы p = 0 был MSB, просто инвертируйте сдвиги (это работает правильно, потому что ones определяется как unsigned int):

unsigned int getbits(unsigned int x, int p, int n) {
  unsigned int ones = ~(unsigned int)0;
  return x ^ (ones >> p) ^ (ones >> (p+n));
}

примечание: в обоих случаях, если p < 0, p >= sizeof(int)*8, p+n < 0 или p+n >= sizeof(int)*8 результат getbits не определен.

person CAFxX    schedule 01.04.2013
comment
Не дает правильного значения. Я тестирую 182, это 101(101)10 - часть в скобках - это часть, которую нужно перевернуть. Значение, которое я должен получить с invert(182, 4, 3), равно 170. - person sdf89; 01.04.2013
comment
Это потому, что вы считаете MSB как p = 0. Я четко заявил, что считаю младший бит как p = 0. Я исправлю свой ответ. - person CAFxX; 01.04.2013
comment
Виноват. Я считал p справа, но n слева. - person sdf89; 01.04.2013

arrow_upward
0
arrow_downward

Взгляните на «Введение в программирование на C» Стива Саммита и на "В руководстве по указателям и массивам в C". Язык, который они охватывают, немного отличается от сегодняшнего C (также изменились обычаи программирования, машины намного больше, и настоящие мужчины больше не пишут на ассемблере), но многое из того, что они говорят, так же верно сегодня, как было тогда. От "битовых приемов" Шона Андерсона у вас глаза выпучатся. Гарантированно.

person vonbrand    schedule 01.04.2013

arrow_upward
0
arrow_downward

Я выяснил, что было не так в моей реализации (кроме подсчета num с неправильного направления). Это кажется довольно очевидным после того, как я узнал о битах больше.

Когда 1 бит сдвигается влево за пределы диапазона битового поля, он расширяется.

   1000 (8) << 1
== 10000 (16)

bitfield << n умножает bitfield на 2 n раз. Мое выражение ((~bits << (pos+1)) >> num) имеет значения 5, 4 и 3 как значения для bits, pos и num соответственно. Я дважды умножал число размером почти 32-битное int на 2.

person sdf89    schedule 04.04.2013

arrow_upward
0
arrow_downward

как насчет моей функции? я думаю это так хорошо.

unsigned invert(unsigned x,int p,int n)
{
     return (x^((~(~0<<n))<<p+1-n));
}
person Community    schedule 19.06.2014