Quake's blog

Trouble with Bitwise
By Quake, history, 9 years ago, In English

Hey guys, I was looking at solution to the problem BITS: http://mirror.codeforces.com/contest/484/problem/A . I found a line of code i couldn't understand: for(ll i = x ; i <= y ; i += ( ~ i& -~ i)) ans = i;

what does ( ~ i & -~ i ) do ?

Thank You

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

Comments Comments (7)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi :) updation in the for loop :Like i+=(~i&(-(~i)) will give you "next power of 2 minus 1"number.Like from i=(L=2) to let 100000. It will give you 3,7,15,31,63,127 and so....till (<=100000).So every time in loop we will be storing that i.And at end reporting that last stored i.But I wonder how people come up with these kind of things in contests ??

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

    Great Idea, it will not always work properly for the first number, suppose (i=4) the first time this formula will give 5 then the rest is correct. I used this (1LL << (cntBits(i)+1))-1 :D

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Thanks you for pointing out the error.And helping me to improve :) .But I don't understand why everybody using this formula.I mean If it is wrong than there must be counter test cases or trillions of hacks.Don't you think.

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

        I think they are sure that i will be (2^k)-1 for any number k so it will work properly for this case.

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

    As was pointed out, this only happens to work if you start with 2. If you want to know exactly what that line does, let's take a sample sequence, starting with 36:

    36, 37, 39, 47, 63, 127

    Does that mean anything to you? No? What if I write it in binary?

    100100, 100101, 100111, 101111, 111111, 1111111

    Can you see what's happening now?

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

      ffao Would you mind telling me that how do you guys up with these kind of expression during a contest in which this is the easiest problem (Div1 A).I mean to say that is this any standard hack that i don't know or you guys build it by your own at that time.

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

        I guess that it is partially both.

        The most difficult part is (x&-x). It extracts least significant 1 from x. If negative numbers are represented using two's complement, then -x = (~x)+1. x&(~x)=0 but adding 1 clears lowest block of 1 and sets lowest 1 in ~x which was lowest 0 in x.

        Knowing that (x & -x) extracts lowest 1, it is easy to come up with rest of the expression during contest.

        (x&-x) extracts lowest 1

        (~x&-~x) extracts lowest 0

        x += (~x&-~x) sets lowest 0 to 1

        There is an easier way to set lowest 0 to 1 which doesn't rely how language or cpu represents negative numbers. x |= (x+1) also sets lowest 0 to 1.

        → Reply