Stack Overflow
Stack Overflow

Questions tagged [bitcount]

42 questions
171
votes
13 answers

Fast way of counting non-zero bits in positive integer

I need a fast way to count the number of bits in an integer in python. My current solution is bin(n).count("1") but I am wondering if there is any faster way of doing this?
zidarsk8
  • 3,088
  • 4
  • 23
  • 30
68
votes
7 answers

Minimum bit length needed for a positive integer in Python

1 = 0b1 -> 1 5 = 0b101 -> 3 10 = 0b1010 -> 4 100 = 0b1100100 -> 7 1000 = 0b1111101000 -> 10 … How can I get the bit length of an integer, i.e. the number of bits that are necessary to represent a positive integer in Python?
user288832
  • 929
  • 2
  • 7
  • 9
14
votes
13 answers

calculate number of bits set in byte

I am interested, which is the optimal way of calculating the number of bits set in byte by this way template< unsigned char byte > class BITS_SET { public: enum { B0 = (byte & 0x01) ? 1:0, B1 = (byte & 0x02) ? 1:0, B2 = (byte &…
user466534
11
votes
2 answers

what's the difference between __builtin_popcountll and_mm_popcnt_u64?

I was trying to how many 1 in 512MB memory and I found two possible methods, _mm_popcnt_u64() and __builtin_popcountll() in the gcc builtins. _mm_popcnt_u64() is said to use the CPU introduction SSE4.2，which seems to be the fastest, and…
stonyliu
  • 111
  • 1
  • 2
  • 6
11
votes
2 answers

Counting number of bits: How does this line work ? n=n&(n-1);

I need some explanation how this specific line works. I know that this function counts the number of 1's bits, but how exactly this line clears the rightmost 1 bit? int f(int n) { int c; for (c = 0; n != 0; ++c) n = n & (n - 1); …
BBLN
  • 495
  • 6
  • 19
9
votes
2 answers

Counting 1 bits (population count) on large data using AVX-512 or AVX-2

I have a long chunk of memory, say, 256 KiB or longer. I want to count the number of 1 bits in this entire chunk, or in other words: Add up the "population count" values for all bytes. I know that AVX-512 has a VPOPCNTDQ instruction which counts the…
einpoklum
  • 118,144
  • 57
  • 340
  • 684
9
votes
4 answers

How to get lg2 of a number that is 2^k

What is the best solution for getting the base 2 logarithm of a number that I know is a power of two (2^k). (Of course I know only the value 2^k not k itself.) One way I thought of doing is by subtracting 1 and then doing a bitcount: lg2(n) =…
Egon
  • 1,705
  • 18
  • 32
8
votes
0 answers

Why newer clang is generating one more instruction than just popcntl to count the bits of an int on haswell architecture?

While watching this talk by Matt Godbolt, I was astonished to see that Clang, if instructed to compile for the Haswell¹ architecture, works out that the following code int foo(int a) { int count = 0; while (a) { ++count; a &=…
Enlico
  • 23,259
  • 6
  • 48
  • 102
6
votes
4 answers

When to use parallel counting - MIT HAKMEM for bitcount when memory is an issue?

Bitcounting can be done in several ways, eg. with set bit iterator, unset bit iterator, pre-computed bits with lookup tables or parallel counting. As I have figured out by searching the web, unset bit iterator is fast when there are less unset bits,…
pigelin
  • 143
  • 1
  • 8
6
votes
4 answers

Why is it useful to count the number of bits?

I've seen the numerous questions about counting the number of set bits in an insert type of input, but why is it useful? For those looking for algorithms about bit counting, look here: Counting common bits in a sequence of unsigned longs Fastest…
KushalP
  • 10,976
  • 6
  • 34
  • 27
5
votes
3 answers

Java - Big O of bitCount()?

What is the Big O of bit count? I'm not sure how the method works, but I would assume it is done in O(logn). Specifically with this code (where x = 4, y = 1): return Integer.bitCount(x^y);
data_pi
  • 801
  • 2
  • 11
  • 30
5
votes
3 answers

How does Long.bitCount() finds the number of set bits?

I know this is the code. But I'm not able to understand what it does `public static int bitCount(long i){ i = i - ((i > > > 1) & 0x5555555555555555L); i = (i & 0x3333333333333333L) + ((i > > > 2) & 0x3333333333333333L); …
shri cool
  • 95
  • 2
  • 11
4
votes
3 answers

Comparing binary values in MySQL

Say you have two binary values 001011 001111 How can you get the number of different bits in MySQL? I tried SELECT BIT_COUNT(BINARY 001011 ^ BINARY 001111) This returns 6, while I need a solution that returns 1 in this example.
Sheqel
  • 43
  • 1
  • 3
3
votes
3 answers

How can I use the "builtin" function __builtin_ctzll in a VS C++ Project?

I have found out about __builtin_ctzll to count trailing zeros of a 64bit int really fast through the post Intrinsic to count trailing zero bits in 64-bit integers?. I'm a beginner to C++ and don't know how to include this function. I tried to use…
Paul
  • 41
  • 5
3
votes
1 answer

How does this magic bit counting method work?

While working on the XKCD April Fool's skein hash collision problem I ran across this strange, fast, multiplicative method of counting the set bits in a word: c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf; Why does this work / what's…
Ternary
  • 597
  • 4
  • 8
1
2 3