Is there a built-in python function to count bit flip in a binary string?

user_14084298 0
Viewed 510

Is there a built-in python function to count bit flip in a binary string? The question I am trying to solve is given a binary string of arbitrary length, how can I return the number of bit flips of the string. For example, the bit flip number of '01101' is 3, and '1110011' is 2, etc.

The way I can come up with to solve this problem is to use a for loop and a counter. However, that seems too lengthy. Is there a way I can do that faster? Or is there a built-in function in python that allows me to do that directly? Thanks for the help!

python string
3 Answers

Don't know about a built in function, but here's a one-liner:

bit_flip_count = len([x for x in range(1, len(x0)) if x0[x] != x0[x-1]])
user_175684690

There is a very fast way to do that without any explicit loops and only using Python builtins: you can convert the string to a binary number, then detect all the bit flips using a XOR-based integer tricks and then convert the integer back to a string to count the number of bit flips. Here is the code:

# Convert the binary string `s` to an integer: "01101" -> 0b01101
n = int(s, 2)

# Build a binary mask to skip the most significant bit of n: 0b01101 -> 0b01111
mask = (1 << (len(s)-1)) - 1

# Check if the ith bit of n is different from the (i+1)th bit of n using a bit-wise XOR:
# 0b01101 & 0b01111 -> 0b1101  (discard the first bit)
# 0b01101 >> 1      -> 0b0110
# 0b1101 ^ 0b0110   -> 0b1011
bitFlips = (n & mask) ^ (n >> 1)

# Convert the integer back to a string and count the bit flips: 0b1011 -> "0b1011" -> 3
flipCount = bin(bitFlips).count('1')

This trick is much faster than other methods since integer operations are very optimized compare to a loop-based interpreted codes or the ones working on iterables. Here are performance results for a string of size 1000 on my machine:

ljdyer's solution:    96 us     x1.0
Karl's solution:      39 us     x2.5
This solution:         4 us    x24.0

If you are working with short bounded strings, then there are even faster ways to count the number of bits set in an integer.

user_129395570

Given a sequence of values, you can find the number of times that the value changes by grouping contiguous values and then counting the groups. There will be one more group than the number of changes (since the elements before the first change are also in a group). (Of course, for an empty sequence, this gives you a result of -1; you may want to handle this case separately.)

Grouping in Python is built-in, via the standard library itertools.groupby. This tool only considers contiguous groups, which is often a drawback (if you want to make a histogram, for example, you have to sort the data first) but in our case is exactly what we want. The overall interface of this tool is a bit complex, but in our case we can use it simply:

from itertools import groupby

def changes_in(sequence):
    return len(list(groupby(sequence))) - 1
user_5236120
Related