John had a chocolate bar with the size of 2i. At his birthday party, he
shared this chocolate bar to his friend. But his friend just wanted to taste a
piece of this chocolate bar which had the length of n (1 ≤ n
≤ 1018) so that John had
to break this chocolate bar into pieces to get the piece for his
friend.Unfortunately, this chocolate bar was so breakable that John just can
break it into half each time.
Help him find the smallest length of the chocolate bar
that he needs and the minimum times of breaking the chocolate bar to get the
piece for his friend.
Input. First line contains the number of test cases t. In each of the next t lines, there is one number n.
Output. For every test case, print one line the length of the
chocolate bar and the minimum number of times to break the bar.
Sample Input
3
8
5
7
Sample Output
8 0
8 3
8 3
математика – битовые
операции
Для заданного числа n найдем минимальную степень двойки A = 2len, не меньшую n. Пусть len – количество бит в А. Найдем позицию b младшего единичного бита в числе n (позиции начинаются с нуля). То есть число n делится на 2b, но не делится на 2b+1.
Реализация алгоритма
#include <stdio.h>
int tests, len, b;
long long
n;
int main(void)
{
scanf("%d",&tests);
while(tests--)
{
scanf("%lld",&n);
len = 0;
while((1LL << len) < n) len++;
b = 0;
while((n & (1LL << b)) == 0) b++;
printf("%lld %d\n",1LL << len,len - b);
}
return 0;
}