1

In ANSI C section 2.9, the bitwise operators, I am unable to understand this particular code.

I know how each bitwise operator works, but combinations need some help.

getbits(x, 4, 3)

unsigned getbits(unsigned x, int p, int n) {
    return (x >> (p + 1 - n)) & ~(~0 << n);
}
chqrlie
  • 131,814
  • 10
  • 121
  • 189
Shivam Kumar Shukla
  • 23
  • 2
  • If you know how each bitwise operator works, I don't understand what you're asking. – Jabberwocky Jul 19 '19 at 07:04
  • 2
    @Jabberwocky I believe it's about the function itself, which we have to admit apart from the name couldn't be more cryptic. – joH1 Jul 19 '19 at 07:09

2 Answers2

4

~0 is an int made of binary ones (111...111111)
~0<<n introduces n zeros in the lower bits (111...111000).
~(~0<<n) flips the bits (000...000111)
x>>(p+1-n) shifts x towards the lower bits (00XXX...XXXXXX).
The & operation combines the previous two results: upper zeros are kept as zeros and the lower X bits (facing the ones) are kept as is (00000...000XXX).

Thus this function retrieves a n-bit pattern of x from bit p, but shifted (p+1-n) positions towards lower bits (ie, placed at the lower position).

prog-fh
  • 13,492
  • 1
  • 15
  • 30
2

The function is supposed to extract a bitfield of width n at position p.

There are problems in this function:

  • p + 1 - n seems bogus but it is the number of bits to the right of the bitfield if p is the bit number of the most significant bit in the bitfield, numbered from 0 for the least significant bit..

  • the code has implementation defined behavior if the most significant bit of x is included in the bitfield because 0 is a signed integer. 0U should be used instead.

  • the code does not work to extract a bitfield that has the full width of unsigned int, because shifting by a number of bits greater or equal to the width of the type has undefined behavior. The shift should be split in 2 parts, n - 1 bits and an additional 1 bit. n - 1 will be in the range [0..31] so the variable shift is fully defined.

Here is a more portable version:

// extract `n` bits at position `p`. n in [1..32], p in `[1..32]`
unsigned getbits(unsigned x, int p, int n) {
   return (x >> (p + 1 - n)) & ~(~0U << (n - 1) << 1);
}

Here are the steps:

  • 0U is the unsigned int null constant.
  • ~0U has all its value bits set.
  • ~0 << (n - 1) has all its value bits set except for the n - 1 low order bits, which are cleared.
  • ~0 << (n - 1) << 1 has all its value bits set except for the n low order bits, which are cleared.
  • ~(~0 << (n - 1) << 1) has the n low order bits set.
  • p + 1 - n is the number of bits with lower order than the bitfield
  • x >> (p + 1 - n) shifts the value to the right, leaving the bitfield in the low order bit positions.
  • (x >> (p + 1 - n)) & ~(~0 << (n - 1) << 1) masks the higher order bits, leaving just the bitfield value.

Note that there are other ways to compute the mask:

~0U >> (sizeof(unsigned) * CHAR_BIT - n)

(1U << (n - 1) << 1) - 1
chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • 1
    You should add the explanation that the left shift for the mask is split into `<< (n - 1)` and `<< 1` instead of using a single `<< n` because it would be undefined behavior if `n` was equal to the width of `unsigned`. I think this is not obvious. – Bodo Jul 19 '19 at 07:46
  • `p - 1 - n` will require a minimum of `p == 2` (together with `n == 1`); smaller `p` will result in negative bit shift. Original version seems to be correct in this respect, consider, consider `getbits(n, 0, 1)`. `p` is not the least, but most significant bit to be used. If `p` was least significant bit, we could just shift by `p`. – Aconcagua Jul 19 '19 at 07:47
  • 2
    I agree with `0u` but I cannot understand your reasoning about the 1 based bit numbering. As far as I understand it, the OP's version is 0 based. For example with `x=4+8+16`, `p=4` and `n=3` we obtain `7` which seems correct to me. – prog-fh Jul 19 '19 at 07:48
  • @Aconcagua: indeed, foolish of me, I would personally always specify the bit offset, instead of the most significant bit number. The bits numbers are 0 based as prog-fh commented. Answer amended. – chqrlie Jul 19 '19 at 07:57
  • I would have been very surprised if K&R were wrong ;^) – prog-fh Jul 19 '19 at 07:59