CazadorDivino's blog

bitwise, when we use this ((k >> i) & 1) == 0
By CazadorDivino, history, 10 years ago, In English

In the last codeforces 307 div 2, problem D. One solutione is below, What that mean 

  if (((k >> i) & 1) == 0) res = res * fib % mod;
            else
                res = res * (pow2 - fib) % mod;

in this code.

long pow2 = fastPower(2, n);
        long fib = fibonacci(n + 1);
        long res = 1;
        for (int i = 0; i < l; i++)
            if (((k >> i) & 1) == 0) res = res * fib % mod;
            else
                res = res * (pow2 - fib) % mod;
        if (res < 0) res += mod;
        System.out.println(res);
  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

The >> in (k >> i) is a shift right function on the binary representation of the number k by shifting it right for i times. In the other words, it returns the number that delete the last i digits from the binary representation of k. For examples:

(5 >> 1) returns 2 ( 510 = 1012, after deleting the last digit, it changes to 102, which gives 210. )

(42 >> 3) returns 5 ( 4210 = 1010102, after deleting the last 3 digits, it changes to 1012, which gives 510. )

Second, (x & 1) is a common way to check whether if the last digit in the binary representation of x is 1 or not. It returns 1 if the last digit in the binary representation of x is 1.

So, (((k >> i) & 1) == 0) is determining whether if the last digit in the binary representation of k after deleting the last i digits is zero or one. In the other words, it is checking if the (i + 1)th digit starting from right to the left is zero or not.

Sorry if this is long, but I hope you can understand the logic behind this code :)

→ Reply