牛客 NC16762：托米的位运算（清晰题解）

题目链接：https://ac.nowcoder.com/acm/problem/16762
难度：中等偏思维

简洁版本

已知&的越多，最后结果越小

我们希望最后的b可以被2^v整除

根据贪心思想，v尽可能大就要从高位枚举，每一个数都包含当前位最终b才能包含当前位，尽可能多选择数，因为&后的数会越来越小或者不变

同时维护temp=(1<<i)-1，每个数&temp，判断temp是否等于0，如果等于0表示已经找到，输出答案即可

详细版本(AI整理)

题目翻译成人话

“b 能被 2^v 整除”在位运算里是什么意思？

👉 b 的二进制末尾至少有 v 个 0

举个例子：

b 的二进制	v
1000	3
101000	3
10	1

也就是说：

b 的最低位 1，出现在第 v 位
更低的 0 ~ v-1 位全是 0

所以我们真正要找的是：

选一堆数，让它们按位与后
✅ 第 v 位是 1
✅ 第 0 ~ v-1 位全是 0
✅ v 尽可能大

核心思路（一步一步想）

从高位往低位试

因为我们要 最大化 v，所以很自然地：

先试 v = 30
不行就 v = 29
一直往下

一旦找到第一个可行的 v，就可以直接输出答案。

如何判断某个 v 是否可行？

假设我们现在尝试 v：

第一步：筛数

只保留 第 v 位是 1 的数

因为如果某个数第 v 位是 0，按位与后这一位一定变成 0，就不可能满足条件

第二步：检查低位

我们希望按位与后：

第 0 ~ v-1 位 全变成 0

怎么做？

用一个变量 temp，初始值是 (1<<v) - 1
- 也就是低 v 位全是 1
每加入一个数，就让 temp &= num
如果最终 temp == 0
- 说明低 v 位已经被“按位与没了”
- ✅ v 是可行的

为什么这样是对的？

第 v 位全是 1 → 按位与后第 v 位还是 1
低 v 位被按位与成 0 → 最低位 1 正好在第 v 位
所以 lowbit(b) = 2^v
这正是题目要求的“最大 v”

参考代码（Python）

import sys
input = sys.stdin.readline

input()
nums = list(map(int, input().split()))

res = []

for v in range(max(nums).bit_length() - 1, -1, -1):
    mask = 1 << v
    temp = (1 << v) - 1
    res = []

    for num in nums:
        if num & mask:
            res.append(num)
            temp &= num

    if temp == 0:
        break

if res:
    print(len(res))
    print(*res)
else:
    print(len(nums))
    print(*nums)

题解 | #托米的位运算#