1648. Fenwick Function

The value of Fenwick function for the number n is the maximum power of two that divides n. Given the number n, find its value of Fenwick function.

Input. One number n (0 < n ≤ 2³¹ – 1).

Output. Print the value of Fenwick function for the number n.

Sample input

12

Sample output

4

SOLUTION

bit operations

Algorithm analysis

While n is even, divide it by 2, and count the number of divisions in variable k. The value 2^k is a maximum power of two that divides the original number n.

The problem also can be solved without loops. The operation n & (n – 1) resets in number n the last one bit in its binary notation. The value n – (n & (n – 1)) is the answer.

Algorithm realization

Read input value of n.

scanf("%d",&n);

While the number n is divisible by 2, divide it by 2 (perform a shift one bit to the right) and increase k (the required power of two) by one.

while(n % 2 == 0)

{

n >>= 1;

k++;

}

Print the answer.

printf("%d\n",1 << k);

Realization without a loop

scanf("%d",&n);

res = n - (n & (n - 1));

printf("%d\n",res);