2 << -1 = 0?
Author
I''m trying to create a macro that''ll replace pow(2, n) using bitshifts. Here''s what it looks like so far:
#define pow2(n) 2 << (n - 1)
It works OK unless you pass 0, which then gets turned into 2 << -1. 2^0 is supposed to be 1, and 10 in binary is 2, and 10 shifted -1 to the left would be 01, which is 1, right? So why does 2 << -1 = 0 when it seems like it''d be 1?
I''d hate to have to add a special case to the macro to return 1 if n is 0. Is there something simple I don''t understand?
I''m really not sure about this, but its possible that << only takes positive numbers. I mean, there is >> for a reason right?
So maybe it took the -1 as an underflow and acctaully bit shifted left 2^32-1 times, which would be 0. Really not sure though...
So maybe it took the -1 as an underflow and acctaully bit shifted left 2^32-1 times, which would be 0. Really not sure though...
Author
Arg, of course! Why didn't I think of that! Thanks.
But I'm still curious why my method didn't work. Is it the shifting by -1 that screws it up?
EDIT: Ah, that kinda makes sense. Or maybe it has something to do with 2's complement representation. Or something.
[edited by - BradDaBug on August 6, 2003 4:57:47 PM]
But I'm still curious why my method didn't work. Is it the shifting by -1 that screws it up?
EDIT: Ah, that kinda makes sense. Or maybe it has something to do with 2's complement representation. Or something.
[edited by - BradDaBug on August 6, 2003 4:57:47 PM]
AP''s solution looks like it should work.
Most likely the problem with the OP''s is that the bit shift instruction takes an unsigned int as the number of digits to shift by. So if you pass it -1, it''ll treat that as an unsigned int:
-1 in binary: 11111111
11111111 as an unsigned int: 255
So it''d shift left 255 digits.
PS: Assuming a one byte int, although it really doesn''t matter for the explanation.
Most likely the problem with the OP''s is that the bit shift instruction takes an unsigned int as the number of digits to shift by. So if you pass it -1, it''ll treat that as an unsigned int:
-1 in binary: 11111111
11111111 as an unsigned int: 255
So it''d shift left 255 digits.
PS: Assuming a one byte int, although it really doesn''t matter for the explanation.
Author
Wait, you mean there''s no point in trying to come up with a faster way to raise a number to a power of two than the pow() function? I''ve never seen the code for pow(), but doesn''t it involve multiplying? Even if it didn''t do any multiplying, the shift would be faster than the function call, woudln''t it? Or is it inline?
I tested this on Mandrake Linux, gcc version 3.2...
pow(2, 5) results in a procedure call in the output assembly, not in a bit shift. However, I can't find the code of the pow function to see how it works, so it may bit shift internally... though I'm not sure, it returns a double.
This may be unoptimized, but I don't know how to with gcc
[edited by - Ronin Magus on August 6, 2003 7:07:07 PM]
pow(2, 5) results in a procedure call in the output assembly, not in a bit shift. However, I can't find the code of the pow function to see how it works, so it may bit shift internally... though I'm not sure, it returns a double.
This may be unoptimized, but I don't know how to with gcc
[edited by - Ronin Magus on August 6, 2003 7:07:07 PM]
I don''t like #define. I prefer to use a variable. The books I read say to never use #define.
Scott Simontis
Big Joke: C#
Scott Simontis
Big Joke: C#
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
