CODEWITHSUNDEEP
c#countsetbituint32
user1437139
user1437139

Reputation: 437

What is the fastest way to count set bits in UInt32

What is the fastest way to count the number of set bits (i.e. count the number of 1s) in an UInt32 without the use of a look up table? Is there a way to count in O(1)?

Upvotes: 22

Views: 33412

Answers (6)

Jeff Camera
Jeff Camera

Reputation: 5554

As of .NET 7 Int32 (and other integer types) have a static PopCount method so you can just call int.PopCount(int bitMask) without having to write your own algorithm or rely on System.Numerics and unsigned types with BitOperations.

https://learn.microsoft.com/en-us/dotnet/api/system.int32.popcount

Upvotes: 7

dana
dana

Reputation: 18155

A platform independent BitOperations.PopCount is available in Core 3.0 and higher.

Hardware intrinsics are used when available, otherwise it defaults to a software fallback. Currently, both X86/64 and ARM processors are supported.

Source

Full credit to @Mark who mentioned this in a comment to another answer.

Upvotes: 16

Polynomial
Polynomial

Reputation: 28346

In .NET Core 3.0 the x86 popcnt intrinsic has been exposed, allowing you to perform a single-instruction population count calculation on a uint or uint64.

int setBits = System.Runtime.Intrinsics.X86.Popcnt.PopCount(value);

There is also a 64-bit version System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount() that can be used on a ulong when running on a 64-bit CPU.

Upvotes: 24

chandan gupta
chandan gupta

Reputation: 1349

Here is the solution in java to get the set bits of a given number.

import java.util.*;

public class HelloWorld {

static int setBits(int n) {
    int count = 0;
    while(n != 0) {
        count+= ((n & 1) == 1) ? 1 : 0;
        n >>= 1;

    }
    return count;
}

 public static void main(String []args){
     Scanner sc = new Scanner(System.in);
     int n = sc.nextInt();
     System.out.println("Results: " + HelloWorld.setBits(n)); 
 }
}

Upvotes: -3

Manuel Amstutz
Manuel Amstutz

Reputation: 1388

Is a duplicate of: how-to-implement-bitcount-using-only-bitwise-operators or best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

And there are many solutions for that problem. The one I use is:

    int NumberOfSetBits(int i)
    {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

Upvotes: 27

Jon Skeet
Jon Skeet

Reputation: 1503934

The bit-twiddling hacks page has a number of options.

Of course, you could argue that iterating over all 32 possible bits is O(N) in that it's the same cost every time :)

For simplicity, I'd consider the lookup-table-per-byte approach, or Brian Kernighan's neat idea which iterates as many times as there are bits set, which I'd write as:

public static int CountBits(uint value)
{
    int count = 0;
    while (value != 0)
    {
        count++;
        value &= value - 1;
    }
    return count;
}

If you don't like the idea of populating a 256-entry lookup table, a lookup-per-nybble would still be pretty fast. Mind you, it's possible that 8 array lookups might be slower than 32 simple bit operations.

Of course, it's worth testing your app's real performance before going to particularly esoteric approaches... is this really a bottleneck for you?

Upvotes: 28

Related Questions