下载掌阅APP，畅读海量书库
立即打开
IQ：70 目标时间：15分钟
我们来看一下山手线的印章比赛。假设所有车站都有印章，参与者必须在进站的车站和出站的车站盖章。印章在检票口里面，进站后可以在不出站的情况下收集印章。
山手线是东京都内的一条环状地铁线，一共有29个车站。这里假设不能通过山手线换乘其他路线，并且只能在山手线单向通行。参与者购买单程车票，从一个车站到另一个车站，每个车站只能通过一次（中途逆行就算违反规则）。
假设印章卡上能够盖所有车站的印章，且山手线上的各站用1～29按顺序编了号。
如果从1号车站进入，从17号车站出站，则一共有多少种盖章方式（ 图1.3 ）？
图1.3 问题的示意图
① 山手线是环形运行的，靠内侧运行的叫作内环，在其外侧反向运行的叫作外环。我国是右侧通行，所以内环是顺时针，外环是逆时针，而日本是左侧通行，所以内外环运行的方向与我国的情况恰好相反。——编者注
为了简化问题，我们可以把车站想象成笔直的一列，而不是一个圆环。由于不能逆行，所以我们只要考虑参与者在各站是否下车即可，由此便能求出组合数。
比如，在有1、2、3、4、5这5个车站的情况下，组合方式一共有8种，具体如 图1.4 所示。
图1.4 有5个车站的情况
因为我们一定会在进站和出站的两个车站盖章，所以只要思考是否在2号、3号和4号车站下车即可。用2×2×2就能求出结果。也就是说，如果“中间的车站数”有 n 个，组合方式就有2 n 种。
在求2 n 时，用到了移位运算符“<<”。“<<”是左移运算符，1<<3表示将二进制数1左移3位，右侧的空位补零（ 图1.5 ）。
图1.5 左移运算符
左移1位，表示的数就会变成原数的2倍，右移1位，则会缩小为原数的1/2，所以要计算2的 n 次方，只要将二进制数1往左移 n 次就可以了。
在计算 a 的 b 次方时，在使用Ruby的情况下可以写成a ** b，在使用JavaScript的情况下可以写成Math.pow（a, b），但如果底数是2，即如果求的是2的乘方，那么使用移位运算符的处理速度会更快。
※ 根据ES2016，在使用JavaScript的情况下也能写成a ** b的形式。
答案 36863种
除了在本题中用到的移位运算，AND、OR、XOR等位运算（逻辑运算）也很常用。位运算不仅能让代码变得简洁，提高处理速度，还能在一份数据中融入多条信息。
使用位运算容易给人一种“技术狂”的印象，但其实在实际工作中我们经常会用到它。例如，在开发Windows应用程序时，我们经常用位运算判断文件和文件夹的属性。
已经保存的文件会被赋予“只读”“隐藏”等各种属性。这部分是通过FileAttributes枚举来管理的。各类属性使用1, 2, 4, 8, 16, …这种2的乘方的枚举常量来定义。 表1.4 中列出了这些属性，各个属性按比特位赋特定的值。
表1.4 FileAttributes的属性
例如，我们可以按照下面的方式使用AND来判断文件是否设置了只读位。
