Q679: Dropping Balls

/*
    這題要用 binary 來想
    假設 level = 4, times 可能 1~8 但會減1 就是 0~7

    times   binary system  position

                    位數
                    012
      0      1000 + 000     8+0
      1      1000 + 100     8+4
      2      1000 + 010     8+2
      3      1000 + 110     8+6
      4      1000 + 001     8+1
      5      1000 + 101     8+5
      6      1000 + 011     8+3
      7      1000 + 111     8+7
    Run time: 0.090
*/
#include <stdio.h>
int main()
{
    int n;
    int level;
    int times;
    int i;
    int pos;
    int weight;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d%d", &level, &times);

        // 0 to 2^(level-1)-1 讓次數介於這個範圍
        // 就可以用 binary 來表示了
        times--;

        // 要算 leaf 的第一個 node
        // 同時也代表最後一層有幾個node
        pos = 1;
        for ( i = 0; i < level-1; i++)
            pos *= 2;

        // 用 level-1個 bits
        // 因為node 編號最多也才 pos + pos - 1
        bool arr[level-1];

        // assign the bits to be zero
        for ( i = 0; i < level-1; i++)
            arr[i]= false;

        // calculate the times to binary
        for ( i = 0; i < level-1; i++)
        {
            arr[i] = times%2;
            times /= 2;
        }

        // calculate the position
        weight = 1;
        for ( i = level-2; i >= 0; i--)
        {
            pos += weight*arr[i];
            weight *= 2;
        }

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

    }

}