You are not logged in. Please login at www.codechef.com to post your questions!

×

counting set bits

int NumberOfSetBits32(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = ((i + (i >> 4)) & 0x0F0F0F0F);
    return (i*(0x01010101))>>24;
}
unable to understand the above code snipplet.Any one please help.

asked 12 Jun '15, 08:32

pallesai's gravatar image

4★pallesai
176830
accept rate: 17%


The above code uses bitwise properties to count 1s in the number fast. 0x represents hex numbers, 0x5555555 is a sequence of bits 0101010101... similarly 0x3333 represents 0011001100110011 and so on.

Regarding the logic behind this approach check this Link .
It explains the different techniques to count set bits along with the above mentioned algo and their respective efficiency.

link

answered 12 Jun '15, 12:08

abbas's gravatar image

4★abbas
4118
accept rate: 28%

edited 12 Jun '15, 12:07

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×77

question asked: 12 Jun '15, 08:32

question was seen: 1,454 times

last updated: 12 Jun '15, 12:07