bitwise: different behaviour with negative input value

Question

I'm on the Hardware/Software interface course hosted on Coursera, from where i'm sure you've seen a fair few of these questions..

One of the assignments is to determine whether 2's complement integer x can fit into n-bits, using only a subset of operators, etc. I'm doing well, but came across 2 separate approaches, and hit the whiteboard with them both to understand them fully. Then came the confusion.

The function returns 1 if possible to fit, 0 if not.

Method 1 (correct output)

int fooBar(int x, int n) {
    return !(((x << (32-n)) >> (32-n)) ^x);
}

Executed with positive integer

fooBar(5,3)  == 0

Correctly calculates that 5 cannot be represented as a 2's complement 3 bit integer.

Executed with a negative integer

fooBar(-4,3) == 1

Correctly calculates that -4 can be represented as a 2's complement 3 bit integer.

Method 1 Analysis

x=5, n=3

00000000000000000000000000011101    32 - n == 29
10100000000000000000000000000000    x<<29
00000000000000000000000000000101    >> 29


00000000000000000000000000000101    5
             XOR
00000000000000000000000000000101    5
--------------------------------    
00000000000000000000000000000000    0

00000000000000000000000000000001   !0 == answer, 1.

As you can see, this returns 0, as in, no 5 may not be represented as a 2's complement integer within 3 bits.

Method 2 (incorrect output)

int fooBar(int x, int n) {
    return !((x & ~(1 << (32-n))) ^x);
}

Executed with positive integer

fooBar(5,3)  == 1

False positive.

Executed with negative integer

fooBar(-4,3) == 0

False negative.

Method 2 Analysis

x=5, n=3

00000000000000000000000000011101    32 - n == 29

11011111111111111111111111111111    ~(1<<29)
              AND
00000000000000000000000000000101    5
--------------------------------    
00000000000000000000000000000101    5


00000000000000000000000000000101    5
              XOR
00000000000000000000000000000101    5
--------------------------------
00000000000000000000000000000000    0

00000000000000000000000000000001   !0 == answer, 1.

I am compiling with:

gcc version 4.7.2 (Debian 4.7.2-5)

Question

I'm at a loss as to explain the difference in output, when the analysis shows that everything is identical at the bit level, so any hints/tips as to where I can look to shed light on this for myself is highly appreciated.

Thank you for your time!

sc.

Daniel Fischer · Accepted Answer · 2013-04-25 14:28:42Z

3

In method 1, you write

10100000000000000000000000000000    x<<29
00000000000000000000000000000101    >> 29

but that is not correct (note that your analysis would mean fooBar(5,3) == 1).

First, the result of 5 << 29 causes overflow for signed 32-bit (or smaller) ints, which is undefined behaviour.

Next, the result, if the shift creates the indicated bit pattern (as it usually does), would be negative.

Right-shifting negative integers is implementation-defined, common is an arithmetic right shift, that would sign-extend, and here result in

11111111111111111111111111111101    >> 29

which, when xor-ed with 5 gives a non-zero result (and then applying ! produces 0).

Method 2 doesn't work at all, because, leaving aside undefined behaviour for some inputs, all it does is check whether the (32-n)-th bit is set.

answered Apr 25, 2013 at 14:28

Daniel Fischer

185k19 gold badges319 silver badges436 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

swisscheese Over a year ago

Hi Daniel, thanks for your reply which has now set me back on track for cracking this thing in this lifetime :-)

Daniel Fischer Over a year ago

Hint: how far must you shift a positive n-bit two's complement integer to the right to obtain 0? And what is the result of shifting a negative n-bit two's complement integer that far right (assuming arithmetic shift)?

Daniel Fischer Over a year ago

You don't need to shift that far. Write out for example all values a two's complement three-bit integer type can hold, and look closely.

swisscheese Over a year ago

Ah yes, 3 bits for both positive and negative alike it seems (in the case of a 3 bit integer). I'll plug this back in and have a play with things... thanks :)

Collectives™ on Stack Overflow

bitwise: different behaviour with negative input value

Method 1 (correct output)

Method 2 (incorrect output)

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Method 1 (correct output)

Method 2 (incorrect output)

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related