Thursday, March 23, 2006

Some time ago I came across this formula for checking if an integer is a power of two: ((n & -n) == n)

Upon seeing this, of course, I noticed that it was wrongwrongwrong. So I popped into IRC to ask my brother to agree with me, which he did:

(17:00:58) lkbm: One thing iss telling me that '((n & -n) == n)' will check if n (a signed integer, I assume) is a power of two, but wouldn't 0 & -0 == 0?
(17:02:30) Miciah: Absolutely.
(17:02:40) Miciah: Why don't you write some C to try it?
(17:02:49) lkbm: Doing so right now.
(17:02:55) lkbm: Haven't done C in a year.
(17:03:50) Miciah: It is easy stuff.
(17:04:07) lkbm: 'var n = 0;' is wrong.
(17:04:16) lkbm: Let's try 'int n = 0;'
(17:04:17) Miciah: C wants types.
(17:04:39) lkbm: It also wants my "s to match.
(17:04:50) Miciah: If they aren't escaped or quoted,
(17:04:56) Miciah: ...or commented.
(17:05:00) lkbm: Right. Looksl ike we're right though.

Of course, it works for all values but one, and it's trivial to fix. What cleverness.

Oh, and for you ignorant people wondering why it works, look up 'two's compliment' and keep in mind that '&' is a bitwise and.

No comments: