26 Feb 2015 by Eden

Hamming Weight (Bit Count)

Hamming Weight is the number of 1's in the binary representation of a number.

Examples:

Number	Binary Representation	Hamming Weight
9	1001	2
9741	10011000001101	6
0	0	0

Contract

IMathUtilities

int HammingWeight(int value);

Test Cases

ForPositiveNumbers_ShouldCalculateCorrectWeight

Created By K Bonneau

public void ForPositiveNumbers_ShouldCalculateCorrectWeight(IMathUtilities mathUtilities) { Assert.AreEqual(2, mathUtilities.HammingWeight(9)); Assert.AreEqual(3, mathUtilities.HammingWeight(100)); Assert.AreEqual(6, mathUtilities.HammingWeight(9741)); }

ForZero_WeightShouldBeZero

Created By K Bonneau

public void ForZero_WeightShouldBeZero(IMathUtilities mathUtilities) { Assert.AreEqual(0, mathUtilities.HammingWeight(0)); }

ForMaxIntegerValue_WeightShouldBe31

Created By K Bonneau

//The Int32.MaxValue is 1111111111111111111111111111111 i.e 31 1's public void ForMaxIntegerValue_WeightShouldBe31(IMathUtilities mathUtilities) { Assert.AreEqual(31, mathUtilities.HammingWeight(Int32.MaxValue)); }

You must be logged in to add test cases

2 Solutions

26 Feb 2015 by K Bonneau

public class Solution : IMathUtilities { public int HammingWeight(int value) { value = value - ((value >> 1) & 0x55555555); value = (value & 0x33333333) + ((value >> 2) & 0x33333333); return (((value + (value >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } }

Test Case Run Summary

ForPositiveNumbers_ShouldCalculateCorrectWeight

ForZero_WeightShouldBeZero

ForMaxIntegerValue_WeightShouldBe31

download solution

Try this Solution

Comments

26 Feb 2015 by Eden

If lower most bit is one add it to the sum, then shift the bits in the number to remove the lower most bit. Loop till we have shifted out all the 1 bits.

public class Solution : IMathUtilities { public int HammingWeight(int value) { int sum = 0; while(value > 0) { sum += value & 0x01; value >>= 1; } return sum; } }

Test Case Run Summary

ForPositiveNumbers_ShouldCalculateCorrectWeight

ForZero_WeightShouldBeZero

ForMaxIntegerValue_WeightShouldBe31

download solution

Try this Solution

Comments

Add Solution