Hey guys, I was looking at solution to the problem BITS: http://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
Hey guys, I was looking at solution to the problem BITS: http://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
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
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 ??Great Idea, it will not always work properly for the first number, suppose
(i=4)the first time this formula will give5then the rest is correct. I used this(1LL << (cntBits(i)+1))-1:DThanks 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.
I think they are sure that
iwill be(2^k)-1for any numberkso it will work properly for this case.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?
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.
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)=0but adding 1 clears lowest block of 1 and sets lowest 1 in~xwhich was lowest 0 inx.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 0x += (~x&-~x)sets lowest 0 to 1There 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.