Python: Bitwise NOT and List

https://news.ycombinator.com/item?id=147962

by kirubakaran • 18 years ago

24 22 18 years ago

news.ycombinator.com

I realized that instead of using negative numbers to access elements of a list from the end, we can just use bitwise NOT. That looks more symmetrical (and hence beautiful).

For a list x:

First element is x[0]

Last element is x[~0] (instead of x[-1])

You can use x[~0], x[~1], x[~2]... (coz ~0==-1, ~1==-2 etc)

Did you guys know this already or is this my fresh insight? If it is the latter, YAY! :-)

mrtron• 18 years ago

I didn't know that, but I don't know that it really is that helpful. I prefer the Pythonic way of sticking to one method and having anyone be able to understand it.

Good little hack though, if it works for you go nuts! (but document it somewhere and be consistent)

earle• 18 years ago

x | y bitwise or of x and y

x ^ y bitwise exclusive or of x and y

x & y bitwise and of x and y

x << n x shifted left by n bits

x >> n x shifted right by n bits

~x the bits of x inverted

BrandonM3• 18 years ago

I'm not going to vote you down, but honestly, what was this for?

llimllib• 18 years ago

If you used this in source code that I had to maintain, I would curse you every time I saw it.

Just saying.

kirubakaran4• 18 years ago

If you have to maintain my code, I'm sure you'll curse me anyway.

marcus• 18 years ago

Always write your code as if the person who will maintain it is a deranged ax murderer who knows where you live

attack• 18 years ago

Oh you mean the old

x[::~0][~-1]

trick to get the last item. Thought that's what everyone uses.

slashcom• 18 years ago

You can just use x[-1] to do the exact same thing. ~0 = -1 though, hence the reason x[~0] has kind of a nice feel to it.

foonamefoo2• 18 years ago

your humor detection may be broken.

nostrademons• 18 years ago

I believe this'll only work on machines that use 2s-complement arithmetic, which is basically all of them. Just saying...it's theoretically possible to have number representations where ~0 != -1.

foonamefoo2• 18 years ago

That wouldn't matter since we are talking about python, not assembly or C.

BrandonM3• 18 years ago

I would hazard a guess that CPython (the reference implementation) hooks directly into C for bitwise NOT, and therefore, it would matter.

mulligan• 18 years ago

silly me, all this time i've been using x[~-1] to get the first element, x[~-2] to get the second element, and so forth!

thorax• 18 years ago

I didn't know this and I do like it. Especially if it caught on and became more standard.

I'll see if I can get my crew to try it out.

kirubakaran4• 18 years ago

Wow that would be awesome. BTW, I like your startup (bug.gd)... Thanks for that.

jackdied• 18 years ago

Clever, but as others pointed out likely to anger anyone who has to read your code.

NB: python bitwise operations are not super fast like in C. They don't get optimized down to single CPU instructions but instead are looked up like regular type methods (e.g. __str__ and __add__). An "ob[~0]" won't kill you even in a loop but don't bother translating simple math into bit-twiddling because it won't help (and might hurt if it inflates the number of operations).

ijoshua• 18 years ago

I don’t know the details of the compiler, but the negation operator on int objects also has a corresponding method: `__neg__`

-1 == (1).__neg__()

kirubakaran4• 18 years ago

I tried profiling these two functions:

  import cProfile
  
  def flipbits():
      c=0
      for i in range(1,400000):
          b=~i
          c=c+b
      print c

  def negnums():
      c=0
      for i in range(1,400000):
          b=-i
          c=c+b
      print c

  cProfile.run("flipbits()")

140 function calls in 0.175 CPU seconds

  cProfile.run("negnums()")

140 function calls in 0.176 CPU seconds

---

Summary:

Flipping bits is tiny bit faster actually.To make negnums function produce the same result as flipbits, we need to change b=-i to b=-i-1 and this is even slower. Poke holes in my experiment please.

jcl• 18 years ago

I was under the impression that Python will do constant folding when it compiles to bytecode. In that case, shouldn't "~0" be exactly as fast as "-1" at runtime?

riobard• 18 years ago

what a hack! I LIKE this idea! It's neat!

Look at this code I wrote for Project Euler. it checks if a sequence is "palindromic". A "palindromic" sequence reads the same both from left and from right. So the simple idea is to check from the left of the sequence to the middle, and compare each element during the process with ones read from the right. Note here I use Python 2.5 integer division (//) to ensure the index is integer.

Using official Python index syntax, I have to write "s[i] == s[-i-1]" to compare elements on symmetric positions in the sequence.

  def ispalindromic(s):
      return all(s[i] == s[-i-1] for i in range(len(s)//2))

However, using the "bitwise or" trick proposed above, I just write "s[i] == [s~i]", really neat!

  def ispalindromic(s):
      return all(s[i] == s[~i] for i in range(len(s)//2))

kirubakaran4• 18 years ago

> what a hack! I LIKE this idea! It's neat!

Thanks, it means a lot...

Python: Bitwise NOT and List

Related Stories