Bitwise operations and shifts

Question

Im having some trouble understanding how and why this code works the way it does. My partner in this assignment finished this part and I cant get ahold of him to find out how and why this works. I've tried a few different things to understand it, but any help would be much appreciated. This code is using 2's complement and a 32-bit representation.

/* 
 * fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's 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;
}

Solution 1

c = 33 + ~n;

This calculates how many high order bits are remaining after using n low order bits.

((x << c)>>c

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

!(blah ^ x)

This is equivalent to

blah == x

Solution 2

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

  Note two pieces of platform dependence present in this code: 2's-complement platform, 32-bit int type.

• Then ((x << c) >> c is intended to sign-fill those c higher order bits. Sign-fill means that those values of x that have 0 in bit-position n - 1, these higher-order bits have to be zeroed-out. But for those values of x that have 1 in bit-position n - 1, these higher-order bits have to be filled with 1s. This is important to make the code work properly for negative values of x.

  This introduces another two pieces of platform dependence: << operator that behaves nicely when shifting negative values or when 1 is shifted into the sign bit (formally it is undefined behavior) and >> operator that performs sign-extension when shifting negative values (formally it is implementation-defined)

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

Solution 3

Using the bitwise complement (unary ~) operator on a signed integer has implementation-defined and undefined aspects. In other words, this code isn't portable, even when you consider only two's complement implementations.

---

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

If the sign bit is one, the value shall be modified in one of the following ways:

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

-- the sign bit has the value -(2 M ) (two's complement );

-- the sign bit has the value -(2 M - 1) (ones' complement ).

Which of these applies is implementation-defined, as is whether the value with sign bit 1 and all value bits zero (for the first two), or with sign bit and all value bits 1 (for ones' complement), is a trap representation or a normal value.

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

There are actual implementations that reserve that value as a trap representation in the default mode. The notable one I tend to cite is Unisys Clearpath Dordado on OS2200 (go to 2-29). Do note the date on that document; such implementations aren't necessarily ancient (hence the reason I cite this one).

---

According to 6.2.6.2p4, shifting negative values left is undefined behaviour, too. I haven't done a whole lot of research into what behaviours are out there in reality, but I would reasonably expect that there might be implementations that sign-extend, as well as implementations that don't. This would also be one way of forming the trap representations mentioned above, which are undefined in nature and thus undesirable. Theoretically (or perhaps some time in the distant or not-so-distant future), you might also face signals "corresponding to a computational exception" (that's a C standard category similar to that which SIGSEGV falls into, corresponding to things like "division by zero") or otherwise erratic and/or undesirable behaviours...

---

In conclusion, the only reason the code in the question works is by coincidence that the decisions your implementation made happen to align in the right way. If you use the implementation I've listed, you'll probably find that this code doesn't work as expected for some values.

Such heavy wizardry (as it has been described in comments) isn't really necessary, and doesn't really look that optimal to me. If you want something that doesn't rely upon magic (e.g. something portable) to solve this problem consider using this (actually, this code will work for 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;
}

Comments

[SecurityMatt]

Just out of interest, I wonder why they didn't use (x & ~(1 << c)) instead of ((x >> c) << c)? It would have eliminated an intermediate dependency so would have maybe saved a cycle or two on an out-of-order pipelined processor.

[Code-Apprentice]

@SecurityMatt I'm sure there are several ways to accomplish the same thing.

[AnT stands with Russia]

@SecurityMatt: It wouldn't work properly with negative inputs. The purpose of (x << c) >> c is not to zero-out the higher-order bits (as this answer incorrectly states), but rather to sign-fill them. For negative values the filler is 1, not 0. This is exactly what makes this code work for negative values.

[AnT stands with Russia]

@ovgolovin: It works with negative values provided the implementation details enumerated in my answer are there. In general, this is not a portable implementation and in that sens it doesn't work with any values.

[M.M]

The question says "This code is using 2's complement and a 32-bit representation." so your objections are not relevant. ~ may not produce a trap representation in 2's complement (6.2.6.2/1 footnote 53)

[autistic]

@MattMcNabb Don't use informational footnotes to counter normative references.

[M.M]

Fair point , however the value with sign bit set and all value bits zero cannot be produced by this code anyway (under the given conditions).

[autistic]

@MattMcNabb If you continue reading, you might note that I mention the UB of shifting negative values left... Are you saying that's not relevant here?

[autistic]

@MattMcNabb Even so, is this answer still worthy of a downvote, despite raising a concern that is certainly relevant?

[autistic]

@MattMcNabb If so, I'd love to know for which reasons... No, really... Which actual reasons?

[M.M]

Yes. The parts about trap representations and 16-bit are not relevant because OP specified he is running the code on 2's complement 32-bit with inputs that cannot generate a trap representation. The paragraph about left-shifting is relevant but not very substantial. Compare with AnT's second bullet for a more substantial treatment of that issue, which would actually benefit OP. With the irrelevant parts removed, your answer could be a comment.

[autistic]

@MattMcNabb Fair call. I removed the part about 16-bit (quite some time ago, actually), and your argument in support of trap representations is informational only, where-as mine is normative. Anyway, I'm going to leave this here, if for nothing else then as evidence demonstrating the stubbornness of some SO users.

[AnT stands with Russia]

@Seb: Yes, but it is not just that. This implementation also relies on some positive values becoming negative when their high-order bit gets shifted into sign-bit position. This is critical for making this code to reject, for example, (5, 3) input. Of course, formally this is UB as well.

[M.M]

It is normative that 33 + ~n cannot generate a trap representation in 2's complement, for n in the range [1, 32]

[autistic]

@MattMcNabb Does the C standard mention whether or not the ~ operator is required to flip the sign bit, or does it only operate on value bits? Is it something like the shift operators, where the sign bit might or might not be treated as though it's a value bit? When you describe a 32-bit int, are you counting padding bits or not? Does the bitwise complement operator operate upon padding bits? If you're uncertain about the answer of any of these, then you should also be uncertain about the behaviour of this code, even when int is restricted to "32 bits".

[M.M]

It says "The result of the ~ operator is the bitwise complement of its (promoted) operand (that is, each bit in the result is set if and only if the corresponding bit in the converted operand is not set)" - seems pretty clear. I'm not uncertain about the behaviour of the code.

[autistic]

@MattMcNabb The ~ operator is normatively defined to operate reliably upon unsigned integers; if you continue reading from where you quote you'll see: "If the promoted type is an unsigned type, the expression ~E is equivalent to the maximum value representable in that type minus E."... and there is no such clarity for signed types. So is that behaviour equivalent for signed integer types? In that case, 33 + ~n doesn't necessarily mean what you think it does. It might actually be possible to construct a trap representation on some implementation that uses a 32-bit two's complement ...

[autistic]

@MattMcNabb ... representation, even when confined to input values between 1 and 32. If not now, then at some point in the future.

[M.M]

I repeat: it says "each bit in the result is set if and only if the corresponding bit in the converted operand is not set" . That is very clear. The following bit about unsigned integers does not contradict this quote. NB. I won't be commenting further here, arguments like this are lame and I have made my point.

[autistic]

@MattMcNabb I bet you get away with that, sometimes... and by that I mean argumenta ad nauseum. No, you haven't made your point, because you haven't managed to convince me that the bitwise complement operator definitively operates on the sign bit (which is a distinct bit from the value bits in cases where there is a two's complement trap rep); as it is (and unlike the shift operators) it appears to only operate on value bits.