题解

题面描述

给定一个函数 $f$，满足：

• $f(0)=1$；
• 对任意非负整数 $n$，有
  • 若 $x=2n$，则 $f(x)=f(n)$；
  • 若 $x=2n+1$，则 $f(x)=2\,f(n)$。
    现有 $q$ 次询问，每次给定一个非负整数 $x$，求 $f(x)$ 的值。

思路

从递推式看，每向右移一位（除以2），如果末位是1，就要在结果上乘2，否则不变。
因此，$f(x)$ 正好等于
$f(x)=2^{\#\{\text{二进制表示中“1”的个数}\}}\,.$ 记 $\operatorname{popcount}(x)$ 为 $x$ 的二进制 1 的个数，则
$f(x)$ = $2^{\operatorname{popcount}(x)}.$
既然如此，只要对每个 $x$ 调用内建函数统计 1 的个数，然后左移即可。

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;                       // 读入询问次数 q
    while (q--) {
        unsigned int x;
        cin >> x;                   // 读入当前查询的 x
        // __builtin_popcount(x) 计算 x 的二进制中 1 的个数 c
        // 1u << c 即 2^c
        cout << (1u << __builtin_popcount(x)) << '\n';
    }
    return 0;
}

python

import sys
input = sys.stdin.readline

def main():
    q = int(input())                  # 读入查询次数 q
    for _ in range(q):
        x = int(input())              # 读入当前的 x
        # bin(x) 返回形如 '0b1011' 的字符串，count('1') 即统计其中 '1' 的个数
        c = bin(x).count('1')         
        # 1 << c 相当于 2**c，正好是 2 的 c 次幂
        print(1 << c)

if __name__ == "__main__":
    main()

java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(in.readLine());  // 读入查询次数 q
        
        while (q-- > 0) {
            int x = Integer.parseInt(in.readLine());  
            // Integer.bitCount(x) 直接返回 x 的二进制表示中 1 的个数
            int c = Integer.bitCount(x);
            // 1 << c 即将 1 左移 c 位，得到 2^c
            System.out.println(1 << c);
        }
    }
}

题目内容

定义函数 $f(x)$满足以下递归关系: $1.f(0)=1$;

$2.$对于任意非负整数$n$，有$f(2n)=f(n)$;

$3.$对于任意非负整数$n$，有$f(2n +1)= f(n) ×2$

现给定若干次询问，每次询问一个非负整数$x$，请你计算$f(x)$ 的值.

输入描述

第一行输入一个整数 $q(1≦q≦10^5)$，表示询问的次数

接下来$q$行，每行输入一个非负整数$x(0≦x≦10^9)$，表示一次询问。

输出描述

对于每个询问，输出一行一个整数，表示$f(x)$的值.

样例1

输入

3
0 
1 
3

输出

1
2
4

说明

对于$x=0$，由定义有$f(0)=1$。

对于$x=1$，可以表示为$2·0+1$.故

• $f(1)=f(0)×2=1×2=2$。

对于$x=3$，可以表示为$2·1+1$，故

• $f(3)=f(1) ×2=2×2=4$

样例2

输入

2
2
7

输出

2
8

说明

对于$x=2$，可以写作$2×1$，故

• $f(2) =f(1) = 2$;

对于$x=7$，可以写作$2·3+1$且

• $f(3) = f(1)×2=2×2=4$
• 故$f(7) = f(3)×2=4×2=8$