[Tutor] (no subject)

[Alan Gauld]

"Dirk Wangsadirdja" <dirk at pensiun.com> wrote

>I tested it and it works. But I dont understand why it works. Can 
> someone please explain it further? Thanks.

~n means the bitwise complement (or inverse) of n.

This simply means reversing every bit of n so that 1-> 0 and 0->1

This trick relies on the fact that negative numbers are stored 
on computers using a thing called twos-complement (or 
ones-complement sometimes) .  This ensures tjhe leftmost bit 
is always 1 which the PC uses to indicate a negative number. 
Thus to represent -1 we take the  bitwise inverse of 1 and add 1

1 = 0001 ->  1110 + 1 -> 1111

To get back we subtract 1 and then take the bitwise complement

1111-1 -> 1110 -> 0001

But with this trick we omit the initial add by 1 stage so 

range(n) yields 0...n

But the inverse of 0000 is 1111 which is interpreted as -1 by Python
as above, so 0 maps to -1  in decimal!

and thus 1 (0001) becomes 1110 to which python does: 
1110 subtracting 1 becomes 1101, and inverting gives 0010 = -2!

and so on.

So using ~ maps 0,1,2... to -1,-2,-3...

Very, very sneaky and the first time I've sen it done!
(because its so opaque I wouldn't actually recommend it, 
most programmers would struggle to figure out what was going on 
and probably think ~ was a typo for - I suspect)

See wikipedia for more on twos-complement, and the related trick ,
which is also used sometimes, of ones-complement.

-- 
Alan Gauld
Author of the Learn to Program web site
http://www.alan-g.me.uk/