CODEWITHSUNDEEP
cbit-manipulation
swisscheese
swisscheese

Reputation: 331

bitwise: different behaviour with negative input value

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.

Upvotes: 4

Views: 169

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183873

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.

Upvotes: 3

Related Questions