Geek Answers Handbook

Bit inverts function in K & R 2-7 exercises

Exercise 2-7 of the C programming language:

Write a function invert(x,p,n) that returns x with bits n that start at position p inverted (i.e. 1 is changed to 0 and vice versa), leaving the rest unchanged.

I understood the question as follows: I have 182, which is 101(101)10 in binary format, the part in parentheses should be inverted without changing the rest. The return value should be 10101010 then, which is 170 in decimal value.

Here is my attempt:

 #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; }

Seems right (to me), but invert(182, 4, 3) outputs 536870730 . getbits() works fine (this is straight from the book). I wrote down what happens in the expression that I assigned 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)

It should be right, but it is not. I found out that this is happening incorrectly: ((~xpn << (p+1)) >> n) . I do not see how.

Also, I have no idea how generic this code is. My first priority is simply to make this work. Help in this matter is also welcome.

+4
source share
5 answers

((1u<<n)-1) is a bitmask with bits n '1' in RHS. <<p shifts this block from p left. (you must shift from (pn) instead of p if you want to count on the left).

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

There is still a problem where p is greater than the phrase (more than a dictionary shift is undefined), but this should be the responsibility of the caller; -)

In example 101(101)10 with p = 2 and n = 3:

 1u<<n := 1000 ((1u<<n)-1) := 0111 (((1u<<n)-1) <<p) := 011100 original val := 10110110 val ^ mask := 10101010
+4
source

I think you have a “one by one” problem in one of the shifts (this is just a hunch, I'm not quite sure). However, I would keep it simple (I assume that the position of the index p starts with LSB, i.e. p = 0 is 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: If you need p = 0 to be MSB , just invert the shifts (this works correctly, because ones defined as 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)); }

Note: in both cases, if p < 0 , p >= sizeof(int)*8 , p+n < 0 or p+n >= sizeof(int)*8 , the result of getbits is undefined.

+1
source

Take a look at Steve Summit "Introductory C Programming" and Ted Jensen's "Guide to Pointers and Arrays in C" . The language they embrace is slightly different from today's C (programming practices are also evolving, machines are much larger, and real men no longer write assembler), but much of what they say today is just as true as it was then. Sean Anderson "Bit-twisting khaki" will make your eyes bulge. Guaranteed.

0
source

I found out what was wrong with my implementation (other than counting num from the wrong direction). Since then it has become apparent that I learned more about bits.

When 1-bit is shifted to the left, outside the range of bit-bits, it expanded.

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

bitfield << n multiplies bitfield by 2 n times. My expression ((~bits << (pos+1)) >> num) has 5, 4 and 3 as the values ​​for bits , pos and num , respectively. I multiplied a number almost the size of a 32-bit int by 2, twice.

0
source

how about my function? I think this is so good.

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

More articles:


All Articles