Why is the binary equivalent calculation getting incorrect?

Question

I wrote the following program to output the binary equivalent of a integer taking(I checked that int on my system is of 4 bytes) it is of 4 bytes. But the output doesn't come the right. The code is:

#include<iostream>
#include<iomanip>
using namespace std;

void printBinary(int k){
    for(int i = 0; i <= 31; i++){
        if(k & ((1 << 31) >> i))
            cout << "1";
        else 
            cout << "0";
    }
}

int main(){
    printBinary(12);
}

Where am I getting it wrong?

You didn't provide what actually happens and what you were expecting isntead. — dhein, Sep 01 '15 at 12:50
+ Maybe let us know what do you think you are getting wrong? Hard to tell you where you get something wrong if you don't tell us what confuses you... — dhein, Sep 01 '15 at 13:16
@DonReba Pray tell, how many (popular) compilers use something other than C++03 as the default? — Nicu Stiurca, Sep 01 '15 at 17:22
@SchighSchagh, Visual C++. gcc can't do it for compatibility reasons. — Don Reba, Sep 01 '15 at 17:35
@DonReba: How you dare to now even throw in words about Visual C++? Visual C++ isn't even C++ it isn't respecting the iso documents... — dhein, Sep 02 '15 at 09:13

Yu Hao · Answer 1 · 2015-09-02T02:09:32.227

29

The problem is in 1<<31. Because 2³¹ cannot be represented with a 32-bit signed integer (range −2³¹ to 2³¹ − 1), the result is undefined^[1].

The fix is easy: 1U<<31.

_{[1]: The behavior is implementation-defined since C++14.}

edited Sep 02 '15 at 02:09

answered Sep 01 '15 at 09:32

Yu Hao

119,891
44
235
294

3

[Since C++14](http://stackoverflow.com/questions/26331035/why-was-1-31-changed-to-be-implementation-defined-in-c14) there is no UB – M.M Sep 01 '15 at 12:02
4

@MattMcNabb: I don't see the OP tagged as C++14 – dhein Sep 01 '15 at 13:36
4

@MattMcNabb: your phrasing sounds like you want to show that Yu Hao is incorrect. My point is, he isn't since the OP wasn't stating a specific version. – dhein Sep 01 '15 at 13:54
@Zaibis He is incorrect regarding the current version of C++. I am trying to give additional information . – M.M Sep 01 '15 at 22:52
@MattMcNabb: And I tryed to prevent confusion for future readers. So I'd say we did well my friend ;) – dhein Sep 02 '15 at 07:31

score 8 · Answer 2 · edited May 23 '17 at 10:27

8

This expression is incorrect:

if(k & ((1<<31)>>i))

int is a signed type, so when you shift 1 31 times, it becomes the sign bit on your system. After that, shifting the result right i times sign-extends the number, meaning that the top bits remain 1s. You end up with a sequence that looks like this:

80000000 // 10000...00
C0000000 // 11000...00
E0000000 // 11100...00
F0000000 // 11110...00
F8000000
FC000000
...
FFFFFFF8
FFFFFFFC
FFFFFFFE // 11111..10
FFFFFFFF // 11111..11

To fix this, replace the expression with 1 & (k>>(31-i)). This way you would avoid undefined behavior^* resulting from shifting 1 to the sign bit position.

^* C++14 changed the definition so that shifting 1 31 times to the left in a 32-bit int is no longer undefined (Thanks, Matt McNabb, for pointing this out).

edited May 23 '17 at 10:27

Community

1
1

answered Sep 01 '15 at 09:32

Sergey Kalinichenko

714,442
84
1,110
1,523

While it's technically correct explanation looking at how the instructions are executed on the machine, the language standard leaves the behavior undefined for `1 << 31`. From the specs: `The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. [...] Otherwise, if E1 has a signed type and non-negative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.` – nhahtdh Sep 01 '15 at 09:43
@nhahtdh That's why I wrote that this is the behavior on OP's system. – Sergey Kalinichenko Sep 01 '15 at 09:45
I think you should make it more prominent, and also clarify the fact that while your fix may be correct on the OP's system, it is undefined behavior according to the specs. – nhahtdh Sep 01 '15 at 09:53

score 4 · Answer 3 · edited Sep 01 '15 at 16:22

A typical internal memory representation of a signed integer value looks like:

The most significant bit (first from the right) is the sign bit and in signed numbers(like int) it represents whether the number is negative or not. When you shift additional bits sign extension is performed to preserve the number's sign. This is done by appending digits to the most significant side of the number.(following a procedure dependent on the particular signed number representation used).
In unsigned numbers the first bit from the right is just the MSB of the represented number, thus when you shift additional bits no sign extension is performed.

Note: the enumeration of the bits starts from 0, so 1 << 31 replaces your sign bit and after that every bit shift operation to the left >> results in sign extension. (as pointed out by @dasblinkenlight)

So, the simple solution to your problem is to make the number unsigned (this is what U does in 1U << 31) before you start the bit manipulation. (as pointed out by @Yu Hao)

For further reading see signed number representations and two's complement.(as it's the most common)

Why is the binary equivalent calculation getting incorrect?

3 Answers3