I'll attempt a lay explanation of kernighan's trick without referring to hardware logic. 1. Say your odometer is showing 146799. The next reading is 146800.

I'll attempt a lay explanation of kernighan's trick without referring to hardware logic. 1. Say your odometer is showing 146799. The next reading is 146800. If it is 146999, the next reading is 147000. Observe that if you run the odometer in reverse, all trailing 0's get flipped to 9, and the last non-zero digit is decremented. The digits to the left are unaffected. Let's do this in binary. 2. Take any bitstring x, and focus on the last 1 bit. By definition (of 'last'), the bits following that bit are all zeroes. That is, x is of the of the form .....1, .....10, .....100 etc. 3. Now run the odometer in reverse. x-1 is of the form .....0, .....01, .....011 etc. Observe (a) the "...." part remains unchanged. Only the bits following and including the last set 1 are flipped. (b) the position of the last '0' in x-1 is the same position as the last '1' in x. x = 10101100 x-1 = 10101011 4 Bit-wise & the two. The "..." part remains unchanged, the trailing zeroes of 'x' remain unchanged. Therefore, only the last 1 of x is set to 0 x&x-1 = 10101000 5. In a loop, compute x &= x-1. In each iteration, it sets the last bit in x to zero. Count the number of iterations until x == 0.