Frez's blog

By Frez, history, 9 years ago, In English

Hi.

I'm very interested in binary representation of numbers.I see some attractive formula and methods such as :

  • (x)&(-x) return smallest significant of x that is 1 !

  • use binary for create all subsets of a small set :)

  • ...

I want to learn more, so create this blog for sharing interest knowledges and making it worth post for competitive programmers. also I want to know is there a relation about remainder of numbers or divisibility of them in binary ? ( for example in decimal we know a number is divisible by 5 when it's last digit is 0 or 5 )

  • Vote: I like it
  • +6
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it
int bitCount(int i)
{
	i = i - ((i >> 1) & 0x55555555);
	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
	return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Count the number of ones in the binary representation of i.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh interesting ... is there a proof for this formula?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    not faster than __builtin_popcount(i) in MinGW and slower than __popcnt(i) in MSVC.

    It means that in MinGW __builtin_popcount is not a single call to POPCNT instruction, but some kind of bit magic like your function. yet another MinGW issue

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you test it?

      ideone.com

      And here in Codeforces Custom Test, i < 1000000000:

      14846928128
      2.771
      14846928128
      2.098
      
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        n = 109 doesn't look like realistic constraint, and for 107...108 there is no meaningful difference. Anyway, MSVC is more than 2 times faster in this case.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Frez (previous revision, new revision, compare).

»
9 years ago, # |
Rev. 4   Vote: I like it +2 Vote: I do not like it

for set/turn on the j-th item of the set, use to bitwise OR operation S |= (1<<j) S = 5 (base 10) = 101 (base 2) j = 3 (base 10) = 011 (base 2) ------------- OR S = 7 (base 10) = 111 (base 2) --------------------------- To check if the j'th item of the set is on,use the bitwise AND operation P = S & (1<<j) S = 5 (base 10) = 101 (base 2) j = 2 , 1<<j = 100 (base 2) ------------- AND p = 8 (base 10) = 100 no Ziro ,the 3rd item is 1 --------------------------- multiply & divide by 2 s*2 --> s<<1 s/2 --> s>>1 s/pow(2,n) --> s>>n s*pow(2,n) --> s<<n ---------------------------
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

You can find many tricks in Hacker's Delight book by Henry S. Warren.

»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is really interesting!
    Thank you for sharing this. Bookmarked.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks very beautiful!

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

A good article-sized read is the relevant TopCoder tutorial by bmerry.

For a more thorough study, the Hacker's Delight book mentioned before is the way to go.