获取整数的第n位二进制位

Question

我有一个很大的整数 a，还有一个（相对较小的）整数 n。

请问用原生的Python，获取 a 的二进制表示中从右边数的第 n 位，最快的方法是什么？

Answer 1

把某个比特位移动到最后一个位置，同时把其他的都去掉：

bit = (a >> n) & 1

这里假设比特位是按照常规方式编号的，也就是说，最不重要的比特位是第0位。

编辑：我不确定这是不是你用的Python版本中最快的方法，但至少这是最简单明了的方法。根据你的Python版本以及a和n的具体值，可能会有更快的方法，具体可以参考John Machin的回答。

Answer 2

你问的是最快的方法，估计是想用现代版本的Python。现代的Python可以处理长度不固定的整数，所以传统的做法可能不太适用。对一个大数字进行位移操作是比较耗费资源的，而对1进行位移操作则比较便宜。下面是一些使用 -mtimeit 的输入和相应的输出。第一个是一个简写的例子：

windows command prompt>\python27\python -mtimeit -s"a=10**20;n=3" "(a>>n)&1"
1000000 loops, best of 3: 0.238 usec per loop

-s"a=10**20;n=3" "(a>>n)&1"
0.238 usec 

-s"a=10**20;n=3" "not not(a & (1 << n))"
0.154 usec 

-s"a=10**200;n=3" "(a>>n)&1"
0.382 usec 

-s"a=10**200;n=3" "not not(a & (1 << n))"
0.155 usec 

-s"a=10**10;n=3" "(a>>n)&1"
0.231 usec 

-s"a=10**10;n=3" "not not(a & (1 << n))"
0.156 usec 

-s"a=10**9;n=3" "(a>>n)&1"
0.0801 usec

-s"a=10**9;n=3" "not not(a & (1 << n))"
0.0938 usec

-s"a=2**1000;n=64" "(a>>n)&1"
0.446 usec

-s"a=2**1000;n=64" "not not(a & (1 << n))"
0.255 usec

如果 not not(foo) 让你感到困惑，或者你真的想要一个 int 类型的结果而不是 bool，你可以用 1 if foo else 0；这个方法只会稍微慢一点。