Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Regarding bit masking in C. Why (~(~0 << N)) is preferred than ((1 << N) -1)?

Tags:

c

bitmask

I do know that ~0 will evaluate the maximum word sized bit 1s (and thus takes caring of portability), but I am still not getting why ((1 << N) - 1) is discouraged?

Please share if you used the second form and got into any trouble.

like image 221
MS. Avatar asked Oct 05 '11 09:10

MS.


3 Answers

Look at these lines:

1. printf("%X", ~(~0 << 31) );
2. printf("%X", (1 << 31) - 1 );

Line 1 compiles and behaves like expected.

Line 2 gives the warning integer overflow in expression.

This is because 1 << 31 is treated by default as a signed int, so 1 << 31 = -2147483648, which is the smallest possible integer.

As a result, resting 1 causes an overflow.

like image 158
Dennis Avatar answered Nov 20 '22 17:11

Dennis


The first form is definitely not preferred, and I would go so far as to say it should never be used. On a ones complement system that does not support negative zero, ~0 may very well be a trap representation and thus invoke UB when used.

On the other hand, 1<<31 is also UB, assuming int is 32-bit, since it overflows.

If you really mean 31 as a constant, 0x7fffffff is the simplest and most correct way to write your mask. If you want all but the sign bit of an int, INT_MAX is the simplest and most correct way to write your mask.

As long as you know the bitshift will not overflow, (1<<n)-1 is the correct way to make a mask with the lowest n bits set. It may be preferable to use (1ULL<<n)-1 followed by a cast or implicit conversion in order not to have to worry about signedness issues and overflow in the shift.

But whatever you do, don't use the ~ operator with signed integers. Ever.

like image 23
R.. GitHub STOP HELPING ICE Avatar answered Nov 20 '22 17:11

R.. GitHub STOP HELPING ICE


I would discourage both, shift or complement operations on signed values is simply a bad idea. Bit patterns should always be produced on unsigned types and (if even necessary) then transposed to the signed counter parts. Then using the primitive types is also no so good as an idea because usually on bit patterns you should control the the number of bits that you are handling.

So I'd always do something like

-UINT32_C(1)
~UINT32_C(0)

which are completely equivalent and at the end this comes just to use UINT32_MAX and Co.

Shift is only necessary in cases you don't shift fully, something like

(UINT32_C(1) << N) - UINT32_C(1)
like image 1
Jens Gustedt Avatar answered Nov 20 '22 17:11

Jens Gustedt