Java Glossary : bit count

Last updated 2004-06-28 by Roedy Green ©1996-2004 Canadian Mind Products

Java definitions: 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

You are here : home : Java Glossary : B words : bit count.

bit count

The number of = 1 bits in a number. Here are two ways to calculate it. The collapsing partial parallel sums method looks horribly complicated but it works 5 times faster than the classic method. Here is the partial sum collapsing method:

/**
 * Counts number of 1 bits in a 32 bit unsigned number.
 *
 * @param x unsigned 32 bit number whose bits you wish to count.
 *
 * @return number of 1 bits in x.
 * @author Roedy Green email
 */
public static int countBits(int x )
   {
   // collapsing partial parallel sums method
   // collapse 32x1 bit counts to 16x2 bit counts, mask 01010101
   x = (x >>> 1 & 0x55555555) + (x & 0x55555555);
   // collapse 16x2 bit counts to 8x4 bit counts, mask 00110011
   x = (x >>> 2 & 0x33333333) + (x & 0x33333333);
   // collapse 8x4 bit counts to 4x8 bit counts, mask 00001111
   x = (x >>> 4 & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
   // collapse 4x8 bit counts to 2x16 bit counts
   x = (x >>> 8 & 0x00ff00ff) + (x & 0x00ff00ff);
   // collapse 2x16 bit counts to 1x32 bit count
   return(x >>> 16) + (x & 0x0000ffff);
   }

Here is the classic solution:

/**
 * Counts number of 1 bits in a 32 bit unsigned number.
 *
 * @param x unsigned 32 bit number whose bits you wish to count.
 *
 * @return number of 1 bits in x.
 * @author Roedy Green email
 */
public static int countBits2(int x )
   {
   // classic shift method
   int result = 0;
   for ( int i=0; i<32; i++ )
      {
      result += x & 1;
      x >>>= 1;
      }
   return result;
   }

Here is an algorithm what works quickly when there are only a few bits turned on.

view

binary ¤ power ¤ Tim Tyler's Bit Utilities ¤ width in bits ¤ width in digits

home	Canadian Mind Products
	mindprod.com IP:[24.87.56.253]
	Your IP:[80.134.30.163]
	You are visitor number 2557.
	Please send errors, omissions and suggestions
	to improve this page to Roedy Green.
	You can get a fresh copy of this page from:	or possibly from your local J: drive mirror:
	http://mindprod.com/jgloss/bitcount.html	J:\mindprod\jgloss\bitcount.html