11

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; }
Improve this question
3
  • 2
    This is heavy wizardry. You're not really supposed to understand it, just accept it as wisdom from up high. Hint: It fits if all bits to the left of position n-1 have the same value as the bit as position n-1. Commented Feb 9, 2013 at 22:56
  • Find out what each operator does (and understand 2's complement), then argue out what would happen to various input values. It takes a lot of practice to be able to easily read something like the above. Commented Feb 9, 2013 at 22:59
  • nice spell! truly magic Commented Sep 21, 2017 at 15:09

4 Answers 4

Reset to default
14 
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
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

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.
@SecurityMatt I'm sure there are several ways to accomplish the same thing.
@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.
@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.
@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.
14

  • 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.

Improve this answer

Comments

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; }
Improve this answer

15 Comments

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)
@MattMcNabb Don't use informational footnotes to counter normative references.
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).
@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?
@MattMcNabb Even so, is this answer still worthy of a downvote, despite raising a concern that is certainly relevant?
|
0

Here's the purely arithmetic approach to answer that same question :

+ 1st parameter - value to be checked for signed bit coverage

+ 2nd parameter - signed bit level to be tested against

+ No division, modulo, bit-masking, or bit-shifting ops were used by the function at all - Just 3 comparison ones (<, <=, ==) , a few additions, and one each of logical negate (!) , ternary (?:) , pre-increment (++_) , pre-decrement (--_) , and exponentiation (^) .

function ____(__, ___, _) { return ((___ = (++_ + _)^___) <= (__ += \ (__ = +__) < !_ ? ___ : --_) + __) == _ } 
-8 4 -7 4 -6 4 -5 4 -4 4 -3 4 -2 4 -1 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4

This approach diverges from existing solutions for testing inputs of either sign against 1 << n instead of 1 << (n - 1)

The logic flow of the function enables _ to contain boolean flag of input's sign without requiring an explicit store.

Caveat - This function is written purely in the mathematical sense of things to illustrate what the equivalent operations are needed to answer the same question, assuming precision of data types are of no concern

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.