Frez's blog

Binary representation
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

Comments Comments (13)
| 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.

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

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

    → Reply
  • »
    »
    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

    → Reply
    • »
      »
      »
      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
      → Reply
      • »
        »
        »
        »
        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.

        → Reply
»
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).

→ Reply
»
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
---------------------------
→ Reply
»
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.

→ Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

https://graphics.stanford.edu//bithacks.html

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

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

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

    thanks very beautiful!

    → Reply
»
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.

→ Reply