• Advertisement
Sign in to follow this  

Odd C++ anamoly

This topic is 3000 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I was fiddling around with C++ today when I executed this particular program.

#include <iostream>
using namespace std;
int main()
{
	for(int x = 1;;x*=2)
	{
		cout << x << endl;
	}
}

I expected this to return an endless stream of numbers, multiplying by 2 with every increment (2,4,8,16,32,ect...). Instead, it returned and endless stream of 0s. Can anyone tell me why this happened? I am way past simple programs like these in my learning of C++, but I was just fiddling around when I discovered this. It really does stump me what's making it do that.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
I expected this to return an endless stream of numbers, multiplying by 2 with every increment (2,4,8,16,32,ect...).
It did.
Quote:
Instead, it returned and endless stream of 0s.
Yep, it did that too.

unsigned char i = 128;
cout << i << endl;
i *= 2;
cout << i << endl; // what is printed here? Why?

Share this post


Link to post
Share on other sites
Looking at the ASM output, the culprit is likely:

mov eax, DWORD PTR _x$[ebp]
shl eax, 1


After so many shifts, it's just shifting 0's into other 0's.

Share this post


Link to post
Share on other sites
Never mind, I figured it out. I feel kinda dumb now. I went and stepped through the program from the beginning, and lo and behold, there's my sequence of numbers multiplying by two, after a certain point, the number went to one negative number, than all zeroes. I'm guessing that is because the number rolled-over because it got too big for the int to hold. Cool. Thanks for your help.

Share this post


Link to post
Share on other sites
It's not that it gets too big to hold; if you used 3 instead of 2, it'd overflow and you'd get a repeating sequence and no 0's.

Bit shifting left by 1 position is a quick way of multiplying by 2. Obviously after so many shifts, all the binary 1's in the number are gone so it ends up as 0 (the reason it goes negative on the last number is because of the sign change).

Share this post


Link to post
Share on other sites
Ah, thanks Gunnie, that makes sense actually. I'm glad I learned something today. So you said that if i used 3 I'd get a repeating sequence? I guess there isn't any way to get numbers that go up to infinity, is there? Not that I'd ever actually need or want them.

Share this post


Link to post
Share on other sites
It'd depend on what you're expecting from "infinity". If you mean a number of infinite length... you'd have to go beyond the 32-bit integer system, I believe.

Are you yet learned in the ways of how integers/etc work on a binary level?

Share this post


Link to post
Share on other sites
If you are not really into Math, the following might make no sense. I'm just posting it in case someone finds it interesting.

In the integer numbers, consider the equivalence relationship where a~b iff a-b is a multiple of 2^32. Now consider the equivalence classes. You'll have the class of all the multiples of 2^32, the class of numbers that can be written as a multiple of 2^32 plus 1, the class of numbers that can be written as a multiple of 2^32 plus 2, etc. There are 2^32 classes. Notice that a multiple of 2^32 + i plus a multiple of 2^32 + j is a multiple of 2^32 + (i+j). This allows us to define addition of classes. Similarly you can define multiplication of classes. These operations provide the set of classes with the structure of a commutative ring.

Probably what an `int' represents in your compiler is one of those classes. In the case of `unsigned int', we represent each class with a number in the range [0,2^32). In the case of `signed int', the representatives are chosen in the range [-2^31,2^31) (not guaranteed by the standard, but I bet that's what signed ints are in your platform).

This group is often called the group of integers modulo 2^32, and it can be written as Z/(2^32).

Now, if you start multiplying a number by 2 repeatedly, you'll end up with a multiple of 2^32, which is 0 in Z/(2^32).

Share this post


Link to post
Share on other sites
I'm not sure about what alvaro says. I could've missed something, but are you maybe implying that you get 0 because there's no number in the "set/group/class" outside of that range?

I did replace the "shl eax, 1" with "imul eax, 2" and got the same result as with the shift, but this could be due to an internal processor optimization (you know how they are).

It might be differences in the way floating points are handled or the way the FPU crunches numbers, but doing the same thing with x as a float and multiplying by 2 produces a pattern in the same way as multiplying x as an int by 3 or 5 or any other non-shift-friendly number.

Can anyone else weigh in on this one?

Share this post


Link to post
Share on other sites
Quote:
Original post by Guinnie
I did replace the "shl eax, 1" with "imul eax, 2" and got the same result as with the shift, but this could be due to an internal processor optimization (you know how they are).


Shifting left by 1 is exactly equivalent to multiplying by two (and so you'll get the same result).

Share this post


Link to post
Share on other sites
I said that myself in one of my previous posts. :P What I meant was that I replaced it with imul to see if there was a difference in how it reacted to the "overflow". Depending on how the processor handles the arithmetic internally, it might have had a similar result as when multiplying by 3 (as it did in the float version). Even though the binary outcome is expected to be identical, it's interesting that the "ALU" seemingly reacts the same, including the sign switch and all. So what comes to mind is that maybe the processor internally performs a shl when multiplying by 2/4/etc, even when the instruction used is imul.

Share this post


Link to post
Share on other sites
Maybe I'll simplify what I said with an example. Imagine you could only represent 10 numbers. You could think of them as the last digit in a number, for instance. How would you define the sum? You would say, 0+0 = 0, 0+1 = 1, ... (similarly for all results less than 10), 5+5 = 0, 5+6 = 1...

Why did I pick 5+6 = 1? Well, pick a number that ends in 5 and add a number that ends in 6, and you'll get a number that ends in 1. Similarly, 5*6 = 0, because a number that ends in 5 times a number that ends in 6 is a number that ends in 0.

The numbers {0,1,2,3,4,5,6,7,8,9} with the operations of addition and multiplication defined above are called Z/(10). Notice that you can as easily define these operations on the numbers {-5,-4,-3,-2,-1,0,1,2,3,4}. When operating modulo 10 (which is what we are doing here), -3 is the same thing as 7, because a number that is obtained as a multiple of 10 minus 3 can also be written as a multiple of 10 plus 7.

What I am saying is that `int' represents Z/(2^32). The operations are well defined, even when there is "overflow". And the results you are getting are exactly what you would expect.

Share this post


Link to post
Share on other sites
Okay, I think I understand how int works now, though the crazy abstract math stuff Alvaro is throwing at me is going way over my head. You were correct, none of that makes any sense to me.

Share this post


Link to post
Share on other sites
I'm not sure I yet undersand how constantly multiplying by 2 eventually produces 0's according to your mathematical explanation, but 3 doesn't. Why is this so?

Share this post


Link to post
Share on other sites
Quote:
Original post by Guinnie
I'm not sure I yet undersand how constantly multiplying by 2 eventually produces 0's according to your mathematical explanation, but 3 doesn't. Why is this so?


Technically, 2 is a nilpotent element of the ring Z/(2^32), while 3 is not, since it's a unit.

Let's try to explain this with integers modulo 8 (3-bit integers). We can build the addition table and the multiplication table:

+ | 0 1 2 3 4 5 6 7 + | 0 1 2 3 4 5 6 7
--+---------------- --+----------------
0 | 0 1 2 3 4 5 6 7 0 | 0 0 0 0 0 0 0 0
1 | 1 2 3 4 5 6 7 0 1 | 0 1 2 3 4 5 6 7
2 | 2 3 4 5 6 7 0 1 2 | 0 2 4 6 0 2 4 6
3 | 3 4 5 6 7 0 1 2 3 | 0 3 6 1 4 7 2 5
4 | 4 5 6 7 0 1 2 3 4 | 0 4 0 4 0 4 0 4
5 | 5 6 7 0 1 2 3 4 5 | 0 5 2 7 4 1 6 3
6 | 6 7 0 1 2 3 4 5 6 | 0 6 4 2 0 6 4 2
7 | 7 0 1 2 3 4 5 6 7 | 0 7 6 5 4 3 2 1

Remember that the way these tables should be interpret is this: 3*5=7 (mod. 8) because if a number x is a multiple of 8 plus 3 and a number y is a multiple of 8 plus 5, their product is a multiple of 8 plus 7:
x=8*X+3
y=8*Y+5
x*y = 64*X*Y+8*5*X+8*3*Y+15 = 8*(64*X*Y+5*X+3*Y+1)+7

Now look at what happens when you start with 1 and multiply by 2 a few times:
1*2=2 (mod. 8)
2*2=4 (mod. 8)
4*2=0 (mod. 8)
0*2=0 (mod. 8)
0*2=0 (mod. 8)
...

If you do this with 3, you'll never get to 0 because if you did get to 0 after n steps, you would get to the equality

3^n = 8*X, for some integer X.

We know that this is not possible because of the unique factorization of integers.

[Edited by - alvaro on December 6, 2009 11:07:23 PM]

Share this post


Link to post
Share on other sites
I'm still not fully following, but I'll trust you know what you're on about. Would the result of the bit shift then be coincidental - or would they be linked on some mathematical level? Thus explaining why both shifting and multiplication overflow in the same way when multiplying by 2, 4 and so on.

Share this post


Link to post
Share on other sites
Multiplication by the base (or a power thereof) is equal to a shift to the left, filling in with zeros to the right, and that applies to any base. Consider for example multiplication by 10 in decimal. That is the same as shifting the digits to the left and filling in a zero at the right. Same with multiplication by 2 in binary; shift to the left and fill in zeros at the right.

Once you start multiplying too much, the digits are shifted outside the allowed range and zeros are being filled in from the right. At some point, there are no digits left, other than the zeros you fill in.

Shifting to multiply is not really a coincidence, but rather a special case of multiplication when the factor you multiply with is a power of the base (2 for binary, 10 for decimal, for example).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement