Low Level Bit Hacks You Absolutely Must Know

You're viewing a comment by John Doe and its responses.

John Doe Permalink
July 01, 2009, 15:06

Sorry to be a party crusher, but you've got a mistake (at least one, I stopped reading.)

=========================================
Bit Hack #6. Turn off the rightmost 1-bit.

y = x & (x-1)
=========================================

Plain wrong. Any X ending with xxx10, when ANDed with (x-1), which obviously ends with xxx01, gives xxx00, ie. a number whose LAST TWO BITS ARE 0.

2d & 1d = 0
10d (0xA) & 9d (0x9) = 8.

Sorry.

Reply to this comment

Comment Responses

Bill Permalink
October 20, 2010, 14:28

Isn't the answer for Bit Hack #6 simply:

y = x & 0xFFFFFFE

(at least for 32-bit values)

Reply to this comment
Tom Kha Gai Permalink
October 20, 2010, 16:36

I do not see any problem.

xxx10 => xxx00, so the rightmost bit is 0 after that, as advertised.

Reply to this comment
jsc42 Permalink
October 21, 2010, 12:52

The problem is with the word 'rightmost' in the title. Like you, I initially assumed that it meant the final bit in the pattern; but what it is intended to mean is "Reset the first found bit that has a value of one when scanning from right to left", but that is a mouthful!

The affected bit in your example of 'xx10' is the '1' between the 'xx' and '0', which (as you correctly point out) is the bit that gets changed to 'xx00'. Rather than being an error, that is the intention of the hack.

Reply to this comment
John C. Permalink
October 21, 2010, 12:54

I had to go back and read Bit Hack#6 again to check, but it DOES do what it says - it turns off the *rightmost 1 bit* (that is, the last binary '1' when reading left to right), which is not necessarily the *rightmost bit* of the number.

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.