Why can't I use the first bit of an int?

Question

I am trying to generate a random number using all the bits of an int. when I use the rand() fuction, it never seems to use the first bit, so I tried to shift the whole thing one place. However, when I try to print the new shifted number it always prints 4294967295, so I guess that's an overflow. Why can't I use that bit, though? is there a way?

If the first bit is not used it works fine, like this (print is before and after the shift of the random number):

00000100001100111111001010010111
00001000011001111110010100101110

but if the first bit is needed, this happens:

01010110100001110011110011011111
42949672950101101000011100111100110111110

please help!! It's technically working, it just prints the number first...

 typedef struct{
    int blocks[NUM_BLOCKS];
} WWord;

void printbits(unsigned int n){
    int i;
    //printf("%u = ",n);
    for(i=SIZE_OF_INT*SIZE_OF_BYTE-1;i>=0;i--){
        int mask = 1<<i;
        int maskedn = n&mask;
        int thebit = maskedn >> i;
        printf("%u",thebit);
    }
    printf("\n");
}

void fillword(WWord *word){
    int i;
    for(i=0; i<NUM_BLOCKS;i++){
        unsigned int ran = rand();
        printbits(ran);
        ran = ran<<1;
        printbits(ran);
        word->blocks[i] = ran;
        //word->blocks[i]<<1;
        printf("\n");
    }
}

signed vs unsigned ints. In a signed int, the high bit is reserved for the sign. In an unsigned int, the high bit is not used for a sign. You are generating and printing unsigned ints, but your `blocks[]` array is storing signed ints. — Remy Lebeau, May 24 '16 at 15:01
@Remy : Yes for the blocks[] thing. You saved me from future troubles! — cmperezg, May 24 '16 at 15:14
_Strictly_ speaking, `unsigned/int` may have padding bits, rare in 2016, so `SIZE_OF_INT*SIZE_OF_BYTE-1` does not necessarily index the most significant bit. A truly portable solution starts with `UINT_MAX`. — chux - Reinstate Monica, May 24 '16 at 15:18
I _think_ `UINT_MAX ^ UINT_MAX/2` will portably make the first `mask` needed, then right shifting `mask` until 0 would work, but would need to test/research that. — chux - Reinstate Monica, May 24 '16 at 15:24
Note: To convert _any_ object into a binary string presentation, [this](http://stackoverflow.com/a/35367414/2410359) may be useful. — chux - Reinstate Monica, May 24 '16 at 15:37

halit · Accepted Answer · 2016-05-24T15:14:44.993

5

It seems you are using int instead of unsigned int in printbits function. So it is converting it to signed int which is using MSB as sign bit. Change those int's to unsigned int it will work.

Change your function as below:

void printbits(unsigned int n){
    int i;
    //printf("%u = ",n);
    for(i=SIZE_OF_INT*SIZE_OF_BYTE-1;i>=0;i--){
        unsigned int mask = 1u<<i;
        unsigned int maskedn = n&mask;
        unsigned int thebit = maskedn >> i;
        printf("%u",thebit);
    }
    printf("\n");
}

edited May 24 '16 at 15:14

answered May 24 '16 at 15:06

halit

177
7

2

Suggest `1< `1u< – chux - Reinstate Monica May 24 '16 at 15:10

Dan Lenski · Answer 2 · 2016-05-24T17:29:34.760

2

Your maskedn is declared to be of type int. This is a signed data type.

However your ran is of type unsigned.

C and C++ treat signed and unsigned integer types differently for the purposes of bit shifts: the behavior of the >> operator for signed integers is implementation-defined according to the C standard, as @chux pointed out in a comment.

However, on most x86 compilers a signed right shift is implemented as an arithmetic shift, which basically means that the sign-bit (the most significant bit in the unsigned representation) is preserved rather than shifted to the right.

If you set the MSB of a signed integer, then you are setting the sign bit, and as you shift to the right you are making copies of that sign bit over and over. See this illustration from Wikipedia

This is why you are getting a very large number, 4294967295, which is (uint32_t)(0xFFFFFFFF), or 32 bits all set to 1.

If you are careful to use unsigned integers everywhere, then you will get the expected behavior in which shifting to the right moves the MSB, rather than copying it.

edited May 24 '16 at 17:29

answered May 24 '16 at 15:17

Dan Lenski

76,929
13
76
124

1

In C, shifting the sign bit right leads to _implementation-defined behavior_, not "the sign-bit ... is preserved as you shift." – chux - Reinstate Monica May 24 '16 at 15:20
Yes, you're right. I think I've come to assume this behavior because most (all?) x86 compilers implement it with `sar`, the arithmetic right shift instruction. I'll clarify this in my answer. – Dan Lenski May 24 '16 at 15:28
1

Use of `(uint32_t)((2L<<32)-1)` is unclear (and undefined). Perhaps you want `(uint32_t) -1`? – chux - Reinstate Monica May 24 '16 at 15:45
I actually mean `2LL`, to guarantee at least 64-bits (even on a 32-bit system), but probably the clearest representation is just `(uint32_t)(0xFFFFFFFF)`. – Dan Lenski May 24 '16 at 17:28

Why can't I use the first bit of an int?

2 Answers2