Archived

This topic is now archived and is closed to further replies.

2 << -1 = 0?

This topic is 5244 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

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?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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...

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
quote:
Original post by Village Specialton
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#


Purists don''t want you to #define. But purists would rather write 20 lines of code where one would suffice, for the sake of purity. There are times when macros are appropriate.

I like pie.

Share this post


Link to post
Share on other sites
But this isn''t one of those times.

unsigned pow2(unsigned n) { return 1 << n; }
will be identical to the macro. You may need to add the keyword "inline" if your optimizer is picky.

Share this post


Link to post
Share on other sites