Unusual behavior with shift-right bitwise operator

▲
2
▼

I'm writing a simple code in C (only using bit-wise operators) that takes a pointer to an unsigned integer x and flips the bit at the nth position n in the binary notation of the integer. The function is declared as follows: 

int flip_bit (unsigned * x, unsigned n);

It is assumed that n is between 0 and 31.

In one of the steps, I perform a shift-right operation, but the results are not what I expect. For instance, if I do 0x8000000 >> 30, I get 0xfffffffe as a result, which are 1000 0000 ... 0000 and 1111 1111 ... 1110, respectively, in binary notation. (The expected result is0000 0000 ... 0010).

I am unsure of how or where I am making the mistake. Any help would be appreciated. Thanks.

Edit 1: Below is the code. 

#include <stdio.h>
#define INTSIZE 31

void flip_bit(unsigned * x,
          unsigned n) {

int a, b, c, d, e, f, g, h, i, j, k, l, m, p, q;
// save bits on the left of n and insert a zero at the end
a = * x >> n + 1;
b = a << 1;

// save bits on the right of n
c = * x << INTSIZE - (n - 1);
d = c >> INTSIZE - (n - 1);

// shift the bits to the left (back in their positions) 
// combine all bits
e = d << n;
f = b | e;

// Isolating the nth bit in its position
g = * x >> n;
h = g << INTSIZE;
// THIS LINE BELOW IS THE ONE CAUSING TROUBLE.
i = h >> INTSIZE - n;

// flipping all bits and removing the 1s surrounding 
// the nth bit (0 or 1)
j = ~i;
k = j >> n;
l = k << INTSIZE;
p = l >> INTSIZE - n;

// combining the value missing nth bit and 
// the one with the flipped one
q = f | p;
* x = q;
}

I'm getting the unusual behavior when I run flip_bit(0x0000004e,0). The line for the shift-right operation in question has comments in uppercase above it.

There is probably a shorter way to do this (without using a thousand variables), but that's what I have now.

Edit 2: The problem was that I declared the variables as int (instead of unsigned). Nevertheless, that's a terrible way to solve the question. @old_timer suggested returning *x ^ (1u << n), which is much better.

c
bit-manipulation
asked on Stack Overflow May 16, 2017 by amucunguzi • edited May 16, 2017 by amucunguzi

3 Answers

▲
2
▼
#include <stdio.h>
int main ( void )
{
    unsigned int x;
    int y;
    x=0x80000000;
    x>>=30;
    printf("0x%08X\n",x);
    y=0x80000000;
    y>>=30;
    printf("0x%08X\n",y);
    return(0);
}

gcc on mint

0x00000002
0xFFFFFFFE

or what about this

#include <stdio.h>
int main ( void )
{
    unsigned int x;
    x=0x12345678;
    x^=1<<30;
    printf("0x%08X\n",x);
}

output

0x52345678
answered on Stack Overflow May 16, 2017 by old_timer • edited May 16, 2017 by old_timer
▲
2
▼

The issue here is that you're performing a right shift on a signed int.

From section 6.5.7 of the C standard:

5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

The bold part is what's happening in your case. Each of your intermediate variables are of type int. Assuming your system uses 2's complement representations for negative numbers, any int value with the high bit set is interpreted as a negative value.

The most common implementation-defined behavior behavior you'll see (and this in fact what gcc and MSVC both do) in this case is that if the high bit is set on a signed value then a 1 will be shifted in on a right shift. This preserves the sign of the value and makes x >> n equivalent to x / 2n for all signed and unsigned values.

You can fix this by changing all of your intermediate variables to unsigned. That way, they match the type of *x and you won't get 1s pushed on to the left.

As for your method of flipping a bit, there is a much simpler way of doing so. You can instead use the ^ operator, which is the bitwise exclusive OR operator.

From section 6.5.11 of the C standard:

4 The result of the ^ operator is the bitwise exclusive OR (XOR) of the operands (that is, each bit in the result is set if and only if exactly one of the corresponding bits in the converted operands is set).

For example:

  0010      1000
^ 1100    ^ 1101
------    ------
  1110      0101

Note that you can use this to create a bitmask, then use that bitmask to flip the bits in the other operand.

So if you want to flip bit n, take the value 1, left shift it by n to move that bit to the desired location then XOR that value with your target value to flip that bit:

void flip_bit(unsigned * x, unsigned n) {
    return *x = *x ^ (1u << n);
}

You can also use the ^= operator in this case which XORs the right operand to the left and assigns the result to the left:

return *x ^= (1u << n);

Also note the u suffix on the integer constant. That causes the type of the constant to be unsigned which helps to avoid the implementation defined behavior you experienced.

answered on Stack Overflow May 16, 2017 by dbush
▲
0
▼

I would do it so 

*x^=1<<n;
answered on Stack Overflow May 16, 2017 by alinsoar

User contributions licensed under CC BY-SA 3.0