Bitwise operations and shifts

Question

I have some problems understanding how and why this code works the way it does. My partner in this assignment finished this part, and I cannot get it to find out how and why it works. I tried several different things to figure this out, but any help would be greatly appreciated. This code uses 2 add-ons and a 32-bit representation.

/* * fitsBits - return 1 if x can be represented as an * n-bit, two complement integer. * 1 <= n <= 32 * Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 2 */ int fitsBits(int x, int n) { int r, c; c = 33 + ~n; r = !(((x << c)>>c)^x); return r; } 

Answer 1

 c = 33 + ~n; 

This calculates how many high order bits remain after using the least significant bit n .

 ((x << c)>>c 

This fills the high order bits with the same value as the signed bit x .

 !(blah ^ x) 

It is equivalent

 blah == x 

Answer 2

• On platform 2's-complement -n equivalent to ~n + 1 . For this reason, c = 33 + ~n on such a platform is actually equivalent to c = 32 - n . This c intended to represent how many higher order bits remain in the 32-bit int value if the lower n bits are occupied.

  Note the two parts of the platform dependency present in this code: 2's-complement platform, a 32-bit int type.

• Then ((x << c) >> c intended to fill these c bits of a higher order. Sign-fill means that those x values ​​that have 0 in the bit position n - 1 , these low-order bits must be reset. But for those x values ​​that have 1 at the bit position n - 1 , these higher order bits should be filled with 1 s. This is important for the code to work correctly for negative x values.

  This introduces two more parts of the platform dependency: the << operator, which behaves well when shifting negative values ​​or when 1 is shifted to the sign bit (formally, this behavior is undefined) and the >> operator, which performs sign-extension when shifting negative values ​​(formally this is determined by the implementation)

• The rest, as mentioned above, is simply a comparison with the original value of x !(a ^ b) equivalent to a == b . If the above transformations did not destroy the original value of x , then x does fit into the n least significant bits of the 2's complement representation.

Answer 3

Using the bitwise complement operator (unary ~ ) for a signed integer has implementation-specific and undefined aspects . In other words, this code is not portable, even if you are considering only two implementations of the add-on.

---

It is important to note that even two complement representations in C can have trap representations. 6.2.6.2p2 even clearly states this :

If the sign bit is one, the value must be changed in one of the following ways:

- the corresponding value with the sign bit 0 is negated (sign and value);

- the sign bit has a value of - (2 M) (two additions);

- the sign bit has the meaning - (2 M - 1) (addition to them).

Which of them relates to the implementation, as well as the value with the sign bit 1 and all bits of the values ​​0 (for the first two) or with the familiar bit and all bits of the value 1 (for one addition), is the representation of the trap or the normal value.

The emphasis is mine. Using trap representations is undefined behavior .

There are actual implementations that save this value as a default view of the trap . Noticeable I tend to refer to Unisys Clearpath Dordado on the OS2200 (go to 2-29) . Pay attention to the date indicated in this document; such implementations are not necessarily ancient (hence the reason why I quote this).

---

According to 6.2.6.2p4 , shifting negative values ​​to the left is undefined behavior. I have not done much research on what behavior actually exists, but I would reasonably expect that there may be implementations that expand, as well as implementations that do not. This would also be one of the ways to form the trap representations mentioned above, which are undefined in nature and therefore undesirable. Theoretically (or perhaps some time in the distant or not so distant future), you may also encounter signals “corresponding to a computational exception” (that the standard category C, similar to the category in which SIGSEGV is located, corresponds to such things as “division” to zero ") or other erratic and / or undesirable behavior ...

---

In conclusion, the only reason the code in the question works is because it matches that the decisions your implementation made match correctly. If you use the implementation that I cited, you will probably find that this code does not work properly for some values.

Such heavy magic (as described in the comments) is actually not necessary, and in fact it does not look so optimal for me. If you want something that doesn't rely on magic (like something portable) to solve this problem, consider using this (in fact, this code will work at least 1 <= n <= 64 ):

 #include <stdint.h> int fits_bits(intmax_t x, unsigned int n) { uintmax_t min = 1ULL << (n - 1), max = min - 1; return (x < 0) * min + x <= max; }