Упражнение 2-7 языка программирования C :
Напишите функцию
invert(x,p,n)
которая возвращаетx
сn
битами, которые начинаются с позицииp
инвертированной (т. Е. 1 изменено на 0 и наоборот), оставляя остальные неизменными.
Я понял такой вопрос: у меня есть 182 101(101)10
в двоичном формате, часть в круглых скобках должна быть инвертирована без изменения остальных. Возвращаемое значение должно быть 10101010
то есть равно 170 в десятичном значении.
Вот моя попытка:
#include 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 <> num); return bitfield ^ mask; }
Кажется правильным (мне), но invert(182, 4, 3)
выходы 536870730
. getbits()
работает отлично (это прямо из книги). Я записал, что происходит в выражении, которое я присвоил y
:
(00000101 << 2) | ((~00000101 <> 3) -- 000000101 is the part being flipped: 101(101)10 00010100 | ((11111010 <> 3) 00010100 | (01000000 >> 3) 00010100 | 00001000 = 00011100 10110110 (182) ^ 00011100 ---------- = 10101010 (170)
Должно быть правильно, но это не так. Я узнал, что это происходит неправильно: ((~xpn <> n)
. Я не понимаю, как это сделать.
Кроме того, я понятия не имею, насколько общий этот код. Мой первый приоритет – просто заставить это дело работать. Помощь в этом вопросе тоже приветствуется.
сдвигает этот блок из По-прежнему существует проблема, когда p больше словаря (смещение больше, чем словосочетание не определено), но это должна быть ответственность вызывающего 😉 Для примера ((1u<
n
'1' битами в RHS. <
p
позиций слева. (вам нужно сдвинуть с (pn)
вместо p, если вы хотите подсчитать слева).
return val ^ (((1u<
101(101)10
с p = 2 и n = 3:
1u<
Я думаю, что у вас есть одна проблема в одной из смен (это просто догадка, я не совсем уверен). Тем не менее, я бы сохранил это просто (я предполагаю, что позиция индекса p
начинается с LSB, то есть p
= 0 является LSB ):
unsigned int getbits(unsigned int x, int p, int n) { unsigned int ones = ~(unsigned int)0; return x ^ (ones << p) ^ (ones << (p+n)); }
edit: Если вам нужно 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
не определен.
Взгляните на «Вводное программирование на С» Стива Саммита и на «Тестирование на указателях и массивах в C» Теда Дженсена. Язык, который они охватывают, немного отличается от сегодняшнего C (также развивались обычаи программирования, машины намного больше, а настоящие мужчины больше не пишут ассемблер), но многое из того, что они говорят, сегодня так же верно, как и тогда. Шон Андерсон «Бит-скручивающиеся хаки» заставит вас задушить глаза. Гарантированный.
Я узнал, что было не так в моей реализации (кроме подсчета числа из неправильного направления). С тех пор стало очевидным, что я узнал больше о битах.
Когда 1-бит сдвинут влево, вне диапазона бит-бит, он расширен.
1000 (8) << 1 == 10000 (16)
bitfield << n
умножает bitfield
на 2 n
раз. Мое выражение ((~bits << (pos+1)) >> num)
имеет 5, 4 и 3 как значения для bits
, pos
и num
соответственно. Я умножал число почти размером 32-битного int на 2, два раза.
как насчет моей функции? я думаю, это так хорошо.
unsigned invert(unsigned x,int p,int n) { return (x^((~(~0<