3

Let's say I have a very very large python integer, in python 2.7 (though if I need to, I don't mind switching to python 3).

Something bigger than say, 2^100000.

What is the fastest way by which I can find the positions of all 1s in it's binary sequence? (example: 24 would be 11000 ---> = [4,5] (or [5,4].. I don't care about order)

At the moment I am using:

sum = whatever_starting_number

while 1:
    val = sum.bit_length()-1
    sum -= 2**val
    mylist.append(val)
    if sum == 0:
        break

this is alright, but it's barely even faster than just taking log2 and subtracting that repeatedly. What I would like to actually do is just look at the bits, skip zeros, record positions of 1s, and not even need to modify the original value.

edit: getting multiple answers, really appreciate it. I'll implement them in a couple timeit tests and this will be updated with results by tomorrow.

Travis Black
  • 705
  • 7
  • 18

4 Answers4

5

Probably not the fastest solution, but fairly simple and seems fast enough (2^1M was instant).

bits = []
for i, c in enumerate(bin(2**1000000)[:1:-1], 1):
    if c == '1':
        bits.append(i)

Just in case the [:1:-1] wasn't clear, it is called "extended slicing", more info here: https://docs.python.org/2/whatsnew/2.3.html#extended-slices.

Edit: I decided to time the 3 solutions posted in answers, here are the results:

import timeit


def fcn1():
    sum = 3**100000
    one_bit_indexes = []
    index = 0
    while sum: # returns true if sum is non-zero
        if sum & 1: # returns true if right-most bit is 1
            one_bit_indexes.append(index)
        sum >>= 1 # discard the right-most bit
        index += 1
    return one_bit_indexes


def fcn2():
    number = 3**100000
    bits = []
    for i, c in enumerate(bin(number)[:1:-1], 1):
        if c == '1':
            bits.append(i)
    return bits


def fcn3():
    sum = 3**100000
    return [i for i in range(sum.bit_length()) if sum & (1<<i)]


print(timeit.timeit(fcn1, number=1))
print(timeit.timeit(fcn2, number=1))
print(timeit.timeit(fcn3, number=1))

For 3^100k:
fcn1: 0.7462488659657538
fcn2: 0.02108444197801873
fcn3: 0.40482770901871845

For 3^1M:
fcn1: 70.9139410170028
fcn2: 0.20711017202120274
fcn3: 43.36111917096423

miken32
  • 42,008
  • 16
  • 111
  • 154
Joe Samanek
  • 1,644
  • 12
  • 16
  • 1
    If you call `enumerate()` you can do away with your counter: `for i,c in enumerate(str(bin(24))[:1:-1], 1):` – Robᵩ Mar 31 '18 at 21:22
  • 1
    No point in calling `str` when `bin` already produces a string. – user2357112 Mar 31 '18 at 21:27
  • Generally if you use string operations to work on numbers you can replace "probably not the fastest solution" with "guaranteed the least efficient solution both memory and performance wise". – Voo Mar 31 '18 at 22:01
  • amazing. it appears that your function is doing much less work, do you think it the reason is because it only looks at a single bit at a time (and for some reason the other strategies do not?), or do you think it is because the bit shift is more expensive than one might think? – Travis Black Mar 31 '18 at 22:55
  • 1
    Hard to say, but my guess would be that both the other solutions require repetitively moving/creating large numbers between different memories (I think sum >>= 1 will create a new number), whereas this solution keeps the large number intact, doesn't create any new large numbers and just works with small numbers (indexes). But really this is just guessing. | Anyway, found this now: https://stackoverflow.com/questions/9829578/fast-way-of-counting-non-zero-bits-in-positive-integer | And it seems that you can't do much better in pure Python. In C it would be a different story. – Joe Samanek Mar 31 '18 at 23:35
  • 1
    You're right. The performance of the string solution is really the best in python, even when playing with `to_bytes` and co. Seems like cpython does not take advantage of the inplace operator so allocates the same number over and over again which has a big performance hit. Upvoted. – Voo Apr 01 '18 at 16:57
4

Maybe this goes fast enough:

mylist = [i for i in range(sum.bit_length()) if sum & (1<<i)]
Robᵩ
  • 163,533
  • 20
  • 239
  • 308
1

You can use bitwise operators.

one_bit_indexes = []
index = 0
while sum: # returns true if sum is non-zero
    if sum & 1: # returns true if right-most bit is 1
        one_bit_indexes.append(index)
    sum >>= 1 # discard the right-most bit
    index += 1

Haven’t tested this, but pretty sure that it will work. Bitwise operations are fast, so this should also be more efficient than calculating and subtracting powers of 2. (Unless your Python interpreter is already doing something smart like transforming your code to replace powers of 2 with bitwise operations).

edit: to make it work for negative numbers, you’ll have to take the absolute value of ‘sum’, first.

Pig
  • 485
  • 4
  • 14
  • Oh, very nice. This is basically what I was trying to come up with myself but using an & with 1 is the clever part I was missing. – Travis Black Mar 31 '18 at 21:31
1

This one is twice as fast as the bin approach:

lookup = [fcn2(i) for i in range(256)]

def fcn4(n):
    nbits = n.bit_length()
    nbytes = nbits//8 + 1
    unsigned_big = n.to_bytes(nbytes, "big", signed=False)
    return [i + rpos
            for i, b in zip(range(0, nbits, 8), unsigned_big)
            for rpos in lookup[b]]

As you can see, it uses another approach to generate a lookup table for all bytes.

For 3^100K:
fcn1: 0.6382
fcn2: 0.0116
fcn3: 0.2926
fcn4: 0.0052

For 3^1M:
fcn1: 62.4622
fcn2: 0.1276
fcn3: 31.8356
fcn4: 0.0582

Adam
  • 53
  • 1
  • 6