Counting non-zero bits into a list of 32-bit integers
Edit: Problem solved, advertise your eyes from the code below, although, haha, I had some things conceptually wrong from the start.
I've been trying for longer than I have to admit to count non-zero bits in a wide range of 32-bit integers, but it always seems a little off.
So, for example, the correct number of non-zero bits for numbers is:
13676 9190872 136669 -17621 -1631 -183 15570 0 495 468656377 -1340216 -91
Will be:
8 12 10 26 25 27 8 0 8 18
However, I always end up with at least a few digits (especially negative ones), no matter what I try.
I am currently using:
def bitCount():
numbers = input().split()
answer = []
for num in numbers:
data = bin(((1 << 32) + int(num)) & -5)
bitCount = 0
for char in data[3:]:
if char == '1':
bitCount += 1
answer.append(str(bitCount))
print(' '.join(answer))
bitCount()
Which for the above number of numbers generates: 7 12 9 25 24 26 8 0 7 18 19 26
What am I doing wrong? How can I solve this problem? I can't imagine this is too complicated, but after hours of searching, reading, and experimenting, I feel like I just need to be missing something obvious. Any help would be greatly appreciated.
source to share
Your whole approach doesn't make sense in Python.
The number of bits 1
in -17621, aka -100010011010101 binary, is 7. If you are expecting 26, you are not asking for the number of bits 1
in the number, you are asking for the number of bits 1
in 32-bit number 2's complement of the 32-bit number, which is interpreted as 32-bit unsigned integer. If you want to be able to do this explicitly in Python. For example, you can use num % 0x100000000
.
Meanwhile, whatever the bit-twiddling trick list you got (1 << 32) + num & -5
is also assuming C int32 math instead of actual integer arithmetic, so this would be wrong. Also, I'm pretty sure you copied it wrong. Also, there is no reason for these tricks in Python odds, it will actually be slower, not faster, but either way, it will be way too slow to be done a million times in a hard loop, and more than fast enough to do multiple times, so this squeeze-last-5% optimization is much more pointless in Python than in C. (Although many of these old tricks actually slow things down in C, well, with modern compilers and processors ...)
And knocking out the original bit 1
by executing [3:]
again assumes you have a 32-bit representation, which is wrong again. (This is why all of your positive numbers were off by 1 - you knock the first 1 bit off.)
So let's just keep it simple:
answer = []
for num in numbers:
data = int(num) % 0x100000000
bits = format(data, 'b')
answer.append(str(bits.count('1')))
print(' '.join(answer))
Note that I used format(data, 'b')
, so I don't need to knock down first 0b
.
Or, if you want to make it more compact:
print(' '.join(str(format(int(num)%0x100000000, 'b').count('1')) for num in numbers))
Either way, you get:
8 12 10 26 25 27 8 0 8 18 20 28
... which has two more numbers than your expected result, but then your input also had two more numbers than your expected result, so I think that might be expected.
source to share
To coax python for two's complement conversion, you can apply a 32 bit 1 bit mask (like 0xFFFFFFFF) to n. As a result, n if n is positive. However, if n is negative, the bitmask operation returns a positive number that has all the same bits as the two complementary representations of the negative number n. So the number of bits is what you expect anyway.
From there you can simply count the bits that come out of the "bin" function.
[bin(n & 0xFFFFFFFF).count("1") for n in numbers]
Result for your example input
[8, 12, 10, 26, 25, 27, 8, 0, 8, 18, 20, 28]
In addition to giving you the answer you expect, this other question suggests bin (n) .count is the fastest way to find the interference weight for an integer
source to share
Try the following:
#!/usr/bin/env python
def bit_counter(number):
suffix = 2
if number < 0:
suffix = 3
bit = bin(number)
counter = 0
for i in bit[suffix:]:
if int(i) == 1:
counter += 1
return counter
def main():
a = 13676
print bit_counter(a)
a = -13676
print bit_counter(a)
if __name__ == "__main__":
main()
It works for negative and non-negative numbers.
source to share
I think you are doing this much more difficult than you need to. I don't understand what I have to do bin((1 << 32) + int(num) & -5)
. As you noticed, it bin(number)
returns the binary representation of a number. So now all you have to do is count the 1st. So this will work:
for num in numbers:
data = bin(num)
bitCount = 0
for char in data:
if char == '1':
bitCount += 1
source to share
The number of bits set to 1 in an integer is known as its Hamming weight or population count .
There are several quick algorithms for performing this calculation. Take a look at the following sources:
- Bit array in Wikipedia article
- Beat Tweedling Hack
- Answers to Question about package # 109023
- Bit manipulation page on the Python wiki.
- Aggregate magic algorithms (optimized for 32-bit integers).
My preferred general algorithms:
def bit_count(n):
"""Return the number of bits set to 1 in the integer number 'n'.
This is called the Hamming weight or the population count of 'n'.
The algorithm performs as many iterations as there are set bits.
References:
The C Programming Language 2nd Ed., Kernighan & Ritchie, 1988.
Peter Wegner in CACM 3 (1960), 322.
"""
assert n >= 0, 'Argument of bit_count() must be non-negative'
count = 0
while n:
n &= n - 1
count += 1
return count
For 32-bit non-negative integers, the following function is faster:
def bit_count_parallel_32(n):
"""Return the number of set bits (1) present in the integer number 'n'.
This algorithm accepts only 32-bit non-negative integer numbers.
"""
assert 0 <= n < 2**32, ('Argument of bit_count_parallel_32() must be '
'non-negative and less than %d (2**32)') % 2**32
n = n - ((n >> 1) & 0x55555555)
n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
return (((n + (n >> 4) & 0x0F0F0F0F) * 0x01010101) & 0xffffffff) >> (8 + 16)
In case anyone needs it, here is the version for 64-bit non-negative integers:
def bit_count_parallel_64(n):
"""Return the number of set bits (1) present in the integer number 'n'.
This algorithm accepts only 64-bit non-negative integer numbers.
"""
assert 0 <= n < 2**64, ('Argument of bit_count_parallel_64() must be '
'non-negative and less than %d (2**64)') % 2**64
n = n - ((n >> 1) & 0x5555555555555555)
n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
return (((n + (n >> 4) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) \
& 0xffffffffffffffff) >> (8 + 16 + 32)
Note, however, that none of these algorithms work with negative integers. If you need to use negative numbers, you can use the previous functions to count the number of bits given in the negative 2 -set representation, for example:
>>> bit_count(-3 & 0xFF)
7
Take a look also at the site dedicated to the excellent book Hacker Delight .
source to share
The easiest way is to use gmpy
:
import gmpy
[gmpy.popcount(n & 0xFFFFFFFF) for n in numbers]
#>>> [8, 12, 10, 26, 25, 27, 8, 0, 8, 18, 20, 28]
It will also be pretty fast compared to string operations.
Another method is to use Numpy:
import numpy
def count_bits_u32(u32):
u32 = (u32 & 0x55555555) + ((u32 & 0xAAAAAAAA) >> 1)
u32 = (u32 & 0x33333333) + ((u32 & 0xCCCCCCCC) >> 2)
u32 = (u32 & 0x0F0F0F0F) + ((u32 & 0xF0F0F0F0) >> 4)
u32 = (u32 & 0x00FF00FF) + ((u32 & 0xFF00FF00) >> 8)
u32 = (u32 & 0x0000FFFF) + ((u32 & 0xFFFF0000) >> 16)
return u32
count_bits_u32(numpy.array(numbers, dtype="uint32"))
#>>> array([ 8, 12, 10, 26, 25, 27, 8, 0, 8, 18, 20, 28], dtype=uint32)
This is likely to be more efficient with large lists of values since it concatenates integers and uses vectorized operations.
source to share