简介
Exchanger，并发工具类，用于线程间的数据交换。
使用
两个线程，两个缓冲区，一个线程往一个缓冲区里面填数据，另一个线程从另一个缓冲区里面取数据。当填数据的线程将缓冲区填满时，或者取数据的线程将缓冲区里的数据取空时，就主动向对方发起交换缓冲区的动作，而交换的时机是，一个缓冲区满，另一个缓冲区空。代码如下，很简单，没有加注释。
public class FillAndEmpty {
Exchanger<DataBuffer> exchanger = new Exchanger<DataBuffer>();
DataBuffer initialEmptyBuffer = DataBuffer.allocate(1024);
DataBuffer initialFullBuffer = DataBuffer.allocate(1024); class FillingLoop implements Runnable {
public void run() {
DataBuffer currentBuffer = initialEmptyBuffer;
try {
while (currentBuffer != null) {
addToBuffer(currentBuffer);
if (currentBuffer.isFull()) {
System.out.println("[FillingLoop](Before)" + currentBuffer);
currentBuffer = exchanger.exchange(currentBuffer);
System.out.println("[FillingLoop](After)" + currentBuffer);
}
}
} catch (InterruptedException ex) {
Thread.currentThread().interrupt();
}
}
} class EmptyingLoop implements Runnable {
public void run() {
DataBuffer currentBuffer = initialFullBuffer;
try {
while (currentBuffer != null) {
takeFromBuffer(currentBuffer);
if (currentBuffer.isEmpty()) {
System.out.println("[EmptyingLoop](Before)" + currentBuffer);
currentBuffer = exchanger.exchange(currentBuffer);
System.out.println("[EmptyingLoop](After)" + currentBuffer);
}
}
} catch (InterruptedException ex) {
Thread.currentThread().interrupt();
}
}
} void start() {
Thread fillingLoopThread = new Thread(new FillingLoop());
Thread emptyingLoopThread = new Thread(new EmptyingLoop()); fillingLoopThread.start();
emptyingLoopThread.start(); try {
Thread.sleep(10);
} catch (InterruptedException e) {
// do nothing
}
fillingLoopThread.interrupt();
emptyingLoopThread.interrupt();
} public void takeFromBuffer(DataBuffer buf) {
buf.take();
} public void addToBuffer(DataBuffer buf) {
buf.add(1);
} private static class DataBuffer {
private final int[] buf;
private final int size;
private int index; private DataBuffer(int size) {
this.size = size;
this.buf = new int[size];
} public static DataBuffer allocate(int size) {
return new DataBuffer(size);
} public boolean isEmpty() {
return index == 0;
} public boolean isFull() {
return index == size - 1;
} public int take() {
if (index > 0) {
return buf[index--];
} return -1;
} public void add(int data) {
if (index < size - 1) {
buf[index++] = data;
}
}
} public static void main(String[] args) {
FillAndEmpty fae = new FillAndEmpty();
fae.start();
}
}
输出如下，交换前后，两个线程所持的数据缓冲区对调。（部分输出未给出）
[EmptyingLoop](Before)com.luoluo.exchanger.FillAndEmpty$DataBuffer@1733c6a5
[FillingLoop](Before)com.luoluo.exchanger.FillAndEmpty$DataBuffer@39bcfec1
[FillingLoop](After)com.luoluo.exchanger.FillAndEmpty$DataBuffer@1733c6a5
[EmptyingLoop](After)com.luoluo.exchanger.FillAndEmpty$DataBuffer@39bcfec1
......
源码解析
常量介绍
private static final int ASHIFT = 7; // 两个有效槽（slot -> Node）之间的字节地址长度（内存地址，以字节为单位），1 << 7至少为缓存行的大小，防止伪共享
private static final int MMASK = 0xff; // 场地（一排槽，arena -> Node[]）的可支持的最大索引，可分配的大小为 MMASK + 1
private static final int SEQ = MMASK + 1; // bound的递增单元，确立其唯一性
private static final int NCPU = Runtime.getRuntime().availableProcessors(); // CPU的个数，用于场地大小和自旋控制
static final int FULL = (NCPU >= (MMASK << 1)) ? MMASK : NCPU >>> 1; // 最大的arena索引
private static final int SPINS = 1 << 10; // 自旋次数，NCPU = 1时，禁用
private static final Object NULL_ITEM = new Object();// 空对象，对应null
private static final Object TIMED_OUT = new Object();// 超时对象，对应timeout
ASHIFT，两个有效的槽之间的地址长度是1 << 7（至少为缓存行的大小，避免伪共享问题，见下面说明）
MMASK，多槽交换可支持的最大索引，大小为MMASK + 1（index从0开始）
SEQ，bound的递增单元，确定其唯一性（高位）
NCPU，CPU的个数
FULL，最大的arena索引，不大于MMASK；arena，一排slot，为的是获得良好的伸缩性，避免所有的线程争用同一个槽位。
SPINS，自旋次数，用于自旋等待，是最轻量的等待，依次是 spin -> yield -> block
伪共享，高速缓存与内存之间是以缓存行为单位交换数据的，根据局部性原理，相邻地址空间的数据会被加载到高速缓存的同一个数据块上（缓存行），而数组是连续的（逻辑，涉及到虚拟内存）内存地址空间，因此，多个slot会被加载到同一个缓存行上，当一个slot改变时，会导致这个slot所在的缓存行上所有的数据（包括其他的slot）无效，需要从内存重新加载，影响性能。
所以，为了避免这种情况，需要填充数据，使得有效的slot不被加载到同一个缓存行上。填充的大小即为1 << 7，如下图所示
数据结构Node
static final class Node {
int index; // arena的索引
int bound; // 记录上次的bound
int collides; // 当前bound下CAS失败的次数
int hash; // 伪随机，用于自旋
Object item; // 当前线程携带的数据
volatile Object match; // 存放释放线程携带的数据
volatile Thread parked; // 挂在此结点上阻塞着的线程
}
index，arena的索引
bound，记录上次的bound
collides，当前bound下CAS失败的次数，最大为m，m（bound & MMASK）为当前bound下最大有效索引，从右往左遍历，等到collides == m时，有效索引的槽位也已经遍历完了，这时需要增长槽位，增长的方式是重置bound（依赖SEQ更新其版本，高位；+1，低位），同时collides重置
hash，伪随机，用于自旋
item，当前线程携带的数据
match，存放释放线程（来交换的线程）携带的数据
parked，挂在此结点上阻塞着的线程，等待被释放
见下图
数据结构Participant
// 每个线程携带一个Node
static final class Participant extends ThreadLocal<Node> {
public Node initialValue() {
return new Node();
}
}
Participant直接继承自ThreadLocal保存当前线程携带的Node，交换操作主要依赖Node的行为
属性介绍
private final Participant participant;// 每个线程携带一个Node
private volatile Node[] arena; // 场地，Node数组
private volatile Node slot;// 槽，单个Node
private volatile int bound;// 当前最大有效arena索引，高8位+SEQ确立其唯一性，低8位记录有效索引
bound，记录最大有效的arena索引，动态变化，竞争激烈时（槽位全满）增加， 槽位空旷时减小。bound + SEQ +/- 1，其高位+ 1（SEQ,oxff + 1）确定其版本唯一性（比如，+1后，又-1，实际上是两个版本的bound，collides要重置的，而且从右向左遍历的索引也要更新，一般来讲，左边槽位比右边槽位竞争激烈，所以要从右向左找，为的是快速找到一个空位置，并尝试占领它，当bound加一又减一后，遍历索引右侧的槽位应该就空出来了，因为大家都往左边靠拢，所以要更新到最右侧，如果没有bound的版本唯一性，便没有索引更新，就一直往左遍历竞争激烈的槽位，还会误判，本来bound应该缩减的，反而又使其增加，于是会很影响效率的。），低位+/-1实际有效的索引（&MMASK）
如下图
exchange方法
public V exchange(V x) throws InterruptedException {
Object v;
Object item = (x == null) ? NULL_ITEM : x; // 转换成空对象
// arena == null, 路由到slotExchange（单槽交换）, 如果arena != null或者单槽交换失败，且线程没有被中断，则路由到arenaExchange（多槽交换），返回null，则抛出中断异常
if ((arena != null || (v = slotExchange(item, false, 0L)) == null)
&& ((Thread.interrupted() || (v = arenaExchange(item, false, 0L)) == null)))
throw new InterruptedException();
return (v == NULL_ITEM) ? null : (V) v;
}
首先判断arena是否为null，如果为null，则调用slotExchange方法，如果arena不为null，或者slotExchange方法返回null，然后判断当前线程是否被中断（中断标记），有则抛出中断异常，没有则继续调用arenaExchange方法，如果该方法返回null，抛出中断异常，最后返回结果。
带超时的exchange方法
public V exchange(V x, long timeout, TimeUnit unit) throws InterruptedException, TimeoutException {
Object v;
Object item = (x == null) ? NULL_ITEM : x;// 转换成空对象
long ns = unit.toNanos(timeout);
// arena == null, 路由到slotExchange（单槽交换）, 如果arena != null或者单槽交换失败，且线程没有被中断，则路由到arenaExchange（多槽交换），返回null，则抛出中断异常
if ((arena != null || (v = slotExchange(item, true, ns)) == null)
&& ((Thread.interrupted() || (v = arenaExchange(item, true, ns)) == null)))
throw new InterruptedException();
if (v == TIMED_OUT)// 超时
throw new TimeoutException();
return (v == NULL_ITEM) ? null : (V) v;
}
同上，加了超时的判断。
slotExchange方法
private final Object slotExchange(Object item, boolean timed, long ns) {
Node p = participant.get(); // 获取当前线程携带的Node
Thread t = Thread.currentThread(); // 当前线程
if (t.isInterrupted()) // 保留中断状态，以便调用者可以重新检查，Thread.interrupted() 会清除中断状态标记
return null;
for (Node q;;) {
if ((q = slot) != null) { // slot不为null, 说明已经有线程在这里等待了
if (U.compareAndSwapObject(this, SLOT, q, null)) { // 将slot重新设置为null, CAS操作
Object v = q.item; // 取出等待线程携带的数据
q.match = item; // 将当前线程的携带的数据交给等待线程
Thread w = q.parked; // 可能存在的等待线程（可能中断，不等了）
if (w != null)
U.unpark(w); // 唤醒等待线程
return v; // 返回结果，交易成功
}
// CPU的个数多于1个，并且bound为0时创建 arena，并将bound设置为SEQ大小
if (NCPU > 1 && bound == 0 && U.compareAndSwapInt(this, BOUND, 0, SEQ))
arena = new Node[(FULL + 2) << ASHIFT]; // 根据CPU的个数估计Node的数量
} else if (arena != null)
return null; // 如果slot为null， 但arena不为null， 则转而路由到arenaExchange方法
else { // 最后一种情况，说明当前线程先到，则占用此slot
p.item = item; // 将携带的数据卸下，等待别的线程来交易
if (U.compareAndSwapObject(this, SLOT, null, p)) // 将slot的设为当前线程携带的Node
break; // 成功则跳出循环
p.item = null; // 失败，将数据清除，继续循环
}
}
// 当前线程等待被释放， spin -> yield -> block/cancel
int h = p.hash; // 伪随机，用于自旋
long end = timed ? System.nanoTime() + ns : 0L; // 如果timed为true，等待超时的时间点； 0表示没有设置超时
int spins = (NCPU > 1) ? SPINS : 1; // 自旋次数
Object v;
while ((v = p.match) == null) { // 一直循环，直到有线程来交易
if (spins > 0) { // 自旋，直至spins不大于0
h ^= h << 1; // 伪随机算法， 目的是等h小于0（随机的）
h ^= h >>> 3;
h ^= h << 10;
if (h == 0) // 初始值
h = SPINS | (int) t.getId();
else if (h < 0 && (--spins & ((SPINS >>> 1) - 1)) == 0)
Thread.yield(); // 等到h < 0, 而spins的低9位也为0（防止spins过大，CPU空转过久），让出CPU时间片，每一次等待有两次让出CPU的时机（SPINS >>> 1）
} else if (slot != p) // 别的线程已经到来，正在准备数据，自旋等待一会儿，马上就好
spins = SPINS;
// 如果线程没被中断，且arena还没被创建，并且没有超时
else if (!t.isInterrupted() && arena == null && (!timed || (ns = end - System.nanoTime()) > 0L)) {
U.putObject(t, BLOCKER, this); // 设置当前线程将阻塞在当前对象上
p.parked = t; // 挂在此结点上的阻塞着的线程
if (slot == p)
U.park(false, ns); // 阻塞， 等着被唤醒或中断
p.parked = null; // 醒来后，解除与结点的联系
U.putObject(t, BLOCKER, null); // 解除阻塞对象
} else if (U.compareAndSwapObject(this, SLOT, p, null)) { // 超时或其他（取消），给其他线程腾出slot
v = timed && ns <= 0L && !t.isInterrupted() ? TIMED_OUT : null;
break;
}
}
// 归位
U.putOrderedObject(p, MATCH, null);
p.item = null;
p.hash = h;
return v;
}
总结
1. 检查slot是否为空（null），不为空，说明已经有线程在此等待，尝试占领该槽位，如果占领成功，与等待线程交换数据，并唤醒等待线程，交易结束，返回。
2. 如果占领槽位失败，创建arena，但要继续【步骤1】尝试抢占slot，直至slot为空，或者抢占成功，交易结束返回。
3. 如果slot为空，则判断arena是否为空，如果arena不为空，返回null，重新路由到arenaExchange方法
4. 如果arena为空，说明当前线程是先到达的，尝试占有slot，如果成功，将slot标记为自己占用，跳出循环，继续【步骤5】，如果失败，则继续【步骤1】
5 当前线程等待被释放，等待的顺序是先自旋（spin），不成功则让出CPU时间片（yield），最后还不行就阻塞（block），spin -> yield -> block
6. 如果超时（设置超时的话）或被中断，则退出循环。
7. 最后，重置数据，下次重用，返回结果，结束。
见下图
arenaExchange方法
private final Object arenaExchange(Object item, boolean timed, long ns) {
Node[] a = arena; // 交换场地，一排slot
Node p = participant.get(); // 获取当前线程携带的Node
for (int i = p.index;;) { // arena的索引，数组下标
int b, m, c;
long j; // 原数组偏移量，包括填充值
// 从场地中选出偏移地址为(i << ASHIFT) + ABASE的内存值，也即真正可用的Node
Node q = (Node) U.getObjectVolatile(a, j = (i << ASHIFT) + ABASE);
if (q != null && U.compareAndSwapObject(a, j, q, null)) { // 此槽位不为null, 说明已经有线程在这里等了，重新将其设置为null, CAS操作
Object v = q.item; // 取出等待线程携带的数据
q.match = item; // 将当前线程携带的数据交给等待线程
Thread w = q.parked; // 可能存在的等待线程
if (w != null)
U.unpark(w); // 唤醒等待线程
return v; // 返回结果， 交易成功
} else if (i <= (m = (b = bound) & MMASK) && q == null) { // 有效交换位置，且槽位为空
p.item = item; // 将携带的数据卸下，等待别的线程来交易
if (U.compareAndSwapObject(a, j, null, p)) { // 槽位占领成功
long end = (timed && m == 0) ? System.nanoTime() + ns : 0L; // 计算出超时结束时间点
Thread t = Thread.currentThread(); // 当前线程
for (int h = p.hash, spins = SPINS;;) { // 一直循环，直到有别的线程来交易，或超时，或中断
Object v = p.match; // 检查是否有别的线程来交换数据
if (v != null) { // 有则返回
U.putOrderedObject(p, MATCH, null); // match重置，等着下次使用
p.item = null; // 清空，下次接着使用
p.hash = h;
return v; // 返回结果，交易结束
} else if (spins > 0) { // 自旋
h ^= h << 1;
h ^= h >>> 3;
h ^= h << 10; // 移位加异或，伪随机
if (h == 0) // 初始值
h = SPINS | (int) t.getId();
else if (h < 0 && // SPINS >>> 1, 一半的概率
(--spins & ((SPINS >>> 1) - 1)) == 0)
Thread.yield(); // 每一次等待有两次让出CPU的时机
} else if (U.getObjectVolatile(a, j) != p)
spins = SPINS; // 别的线程已经到来，正在准备数据，自旋等待一会儿，马上就好
else if (!t.isInterrupted() && m == 0 && (!timed || (ns = end - System.nanoTime()) > 0L)) {
U.putObject(t, BLOCKER, this); // 设置当前线程将阻塞在当前对象上
p.parked = t; // 挂在此结点上的阻塞着的线程
if (U.getObjectVolatile(a, j) == p)
U.park(false, ns); // 阻塞， 等着被唤醒或中断
p.parked = null; // 醒来后，解除与结点的联系
U.putObject(t, BLOCKER, null); // 解除阻塞对象
} else if (U.getObjectVolatile(a, j) == p && U.compareAndSwapObject(a, j, p, null)) {
if (m != 0) // 尝试缩减
U.compareAndSwapInt(this, BOUND, b, b + SEQ - 1); // 更新bound, 高位递增，低位 -1
p.item = null; // 重置
p.hash = h;
i = p.index >>>= 1; // 索引减半，为的是快速找到汇合点（最左侧）
if (Thread.interrupted())// 保留中断状态，以便调用者可以重新检查，Thread.interrupted() 会清除中断状态标记
return null;
if (timed && m == 0 && ns <= 0L) // 超时
return TIMED_OUT;
break; // 重新开始
}
}
} else
p.item = null; // 重置
} else {
if (p.bound != b) { // 别的线程更改了bound，重置collides为0, i的情况如下：当i != m, 或者m = 0时，i = m; 否则，i = m-1; 从右往左遍历
p.bound = b;
p.collides = 0;
i = (i != m || m == 0) ? m : m - 1; // index 左移
} else if ((c = p.collides) < m || m == FULL || !U.compareAndSwapInt(this, BOUND, b, b + SEQ + 1)) { // 更新bound, 高位递增，低位 +1
p.collides = c + 1;
i = (i == 0) ? m : i - 1; // 左移，遍历槽位，m == FULL时，i == 0(最左侧)，重置i = m, 重新从右往左循环遍历
} else
i = m + 1; // 槽位增长
p.index = i;
}
}
}
总结
1. 从场地中选出偏移地址为(i << ASHIFT) + ABASE的内存值，也即第i个真正可用的Node，判断其槽位是否为空，为空，进入【步骤2】；不为空，说明有线程在此等待，尝试抢占该槽位，抢占成功，交换数据，并唤醒等待线程，返回，结束；没有抢占成功，进入【步骤9】
2. 检查索引（i vs m）是否越界，越界，进入【步骤9】；没有越界，进入下一步。
3. 尝试占有该槽位，抢占失败，进入【步骤1】；抢占成功，进入下一步。
4. 检查match，是否有线程来交换数据，如果有，交换数据，结束；如果没有，进入下一步。
5. 检查spin是否大于0，如果不大于0，进入下一步；如果大于0，检查hash是否小于0，并且spin减半或为0，如果不是，进入【步骤4】；如果是，让出CPU时间，过一会儿，进入【步骤4】
6. 检查是否中断，m达到最小值，是否超时，如果没有中断，没有超时，并且m达到最小值，阻塞，过一会儿进入【步骤4】；否则，下一步。
7. 没有线程来交换数据，尝试丢弃原有的槽位重新开始，丢弃失败，进入【步骤4】；否则，下一步。
8. bound减1（m>0），索引减半；检查是否中断或超时，如果没有，进入【步骤1】；否则，返回，结束。
9. 检查bound是否发生变化，如果变化了，重置collides，索引重置为m或左移，转向【步骤1】；否则，进入下一步。
10. 检查collides是否达到最大值，如果没有，进入【步骤13】，否则下一步。
11. m是否达到FULL，是，进入【步骤13】；否则，下一步。
12. CAS bound加1是否成功，如果成功，i置为m+1，槽位增长，进入【步骤1】；否则，下一步。
13. collides加1，索引左移，进入【步骤1】
见下图(看不清图片?鼠标放在图片上面，【右键】 -> 【在新标签页中打开图片(I)】 -> 【点击(+)矢量放大】)
Unsafe
private static final sun.misc.Unsafe U;
private static final long BOUND;
private static final long SLOT;
private static final long MATCH;
private static final long BLOCKER;
private static final int ABASE;
static {
int s;
try {
U = sun.misc.Unsafe.getUnsafe();
Class<?> ek = Exchanger.class;
Class<?> nk = Node.class;
Class<?> ak = Node[].class;
Class<?> tk = Thread.class;
BOUND = U.objectFieldOffset(ek.getDeclaredField("bound"));
SLOT = U.objectFieldOffset(ek.getDeclaredField("slot"));
MATCH = U.objectFieldOffset(nk.getDeclaredField("match"));
BLOCKER = U.objectFieldOffset(tk.getDeclaredField("parkBlocker"));
s = U.arrayIndexScale(ak); // 数组增量地址
ABASE = U.arrayBaseOffset(ak) + (1 << ASHIFT); // 数组首元素偏移地址
} catch (Exception e) {
throw new Error(e);
}
if ((s & (s - 1)) != 0 || s > (1 << ASHIFT))
throw new Error("Unsupported array scale");
}
s为数组中每个元素占用的地址空间大小，ABASE为数组首元素偏移地址，防止伪共享
最后，arena = new Node[(FULL + 2) << ASHIFT]，FULL，<= MMASK，scale，<= 1 << ASHIFT，说明（FULL + 2）<< ASHIFT 个Node，真正可用的是FULL + 2个，实际上是FULL + 1 个，最后一个没有用，也是为了防止伪共享，如果最后一个也使用，那么，其右边并没有填充，别的数据修改可能会影响到它，也即是发生伪共享问题。最大的有效索引是MMASK（bound & MMASK），但m（实际的最大索引）增长到FULL时，不再增长，会循环遍历槽位，尝试交换数据。
伪随机
h ^= h << 1; h ^= h >>> 3; h ^= h << 10;
实际上是xorshift算法，T = (I + La)(I + Rb)(I + Lc)，其中，L代表左移，R代表右移，a, b, c分别代表上式的1，3，10，I代表矩阵{0，1}共32位（int），也即是二进制int，T代表的就是随机算法。翻译过来就是上面的式子：h ^= h << 1; h ^= h >>> 3; h ^= h << 10.
为什么要选用1，3，10呢？
其实，伪随机数，并不是真正的随机，而是通过算法模拟出来的，为了达到随机的效果，希望是周期越大越好。所谓周期指的是，当给定一个输入，得到的输出再作为下一次的输入，如此反复，直到某次输出恰巧等于最初的输入，可以作为随机算法关于随机数的周期。有了这个概念，我们就可以写代码测试下。
直观地推测，int类型最大周期应该是遍历该类型所有的值（0除外，【奇异矩阵】，如果是0的话，输出便一直是0，谈不上随机了），即是max – min = 232 – 1
Java代码
public class PseudoRandom {
private static final Map<Long, StringBuilder> map = new ConcurrentHashMap<>(); public static void random(int a, int b, int c) {
long cnt = 0;
int h = 1;
do {
h ^= h << a;
h ^= h >>> b;
h ^= h << c;
cnt++;
} while (h != 1); StringBuilder builder = map.get(cnt);
if (builder == null) {
builder = new StringBuilder();
map.put(cnt, builder);
} builder.append(" (" + a + ", " + b + ", " + c + ")");
} public static void main(String[] args) {
CountDownLatch latch = new CountDownLatch(11 * 11 * 11);
ExecutorService s = Executors.newFixedThreadPool(10);
for (int i = 1; i < 11; i++) { // i, j ,k实际上应该是31，这里仅为了说明问题，当改成31时，CountDownLatch应该初始化为31 * 31 * 31
for (int j = 1; j < 11; j++) {
for (int k = 1; k < 11; k++) {
final int ii = i;
final int jj = j;
final int kk = k;
s.execute(new Runnable() {
@Override
public void run() {
random(ii, jj, kk);
latch.countDown();
}
});
}
}
} s.shutdown();
try {
latch.await(300, TimeUnit.SECONDS);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
} TreeMap<Long, StringBuilder> t = new TreeMap<Long, StringBuilder>(Collections.reverseOrder());
t.putAll(map); for (Map.Entry<Long, StringBuilder> entry : t.entrySet()) {
System.out.println("[" + entry.getKey() + "]" + entry.getValue().toString());
}
}
}
输出，按周期次数倒序排列，即最大的在前
[4294967295] (1, 3, 10) (2, 7, 7) (2, 7, 9) (5, 9, 7) (7, 1, 9) (7, 7, 2) (7, 9, 5)
[4160749537] (1, 7, 9) (4, 1, 9) (6, 5, 9)
[3900702255] (1, 3, 4) (5, 5, 7) (7, 5, 5)
[3758096377] (1, 9, 2) (2, 9, 1) (7, 7, 9)
[2147483647] (1, 5, 5) (1, 9, 6) (2, 5, 5) (2, 5, 7) (5, 5, 1) (5, 5, 2) (6, 5, 7) (6, 9, 1) (7, 5, 2) (7, 5, 6)
[2147483644] (1, 9, 10)
[2147213313] (2, 5, 3) (3, 5, 2)
[2147188740] (4, 5, 5) (4, 9, 1) (5, 5, 4)
[2145385473] (7, 9, 9)
[2145382404] (1, 5, 9)
[2143288833] (5, 1, 6) (6, 1, 5)
[2139094020] (1, 7, 6)
[2113929153] (1, 5, 4) (4, 5, 1)
[2080374753] (2, 3, 3) (3, 3, 2)
[1997533470] (2, 9, 9)
[1879048185] (2, 5, 9) (4, 7, 9)
[1747831785] (8, 9, 5)
[1610612733] (7, 3, 10)
[1560280902] (3, 5, 5) (5, 5, 3)
[1431655765] (1, 7, 7) (2, 9, 5) (5, 1, 8) (5, 9, 2) (7, 7, 1) (8, 1, 5)
[1431562923] (1, 1, 2) (2, 1, 1)
[1430257323] (3, 9, 7) (7, 9, 3)
[1409286123] (5, 3, 7) (7, 3, 5) (9, 1, 10)
[1339553285] (1, 9, 5) (5, 9, 1)
[1242911789] (3, 7, 10) (5, 3, 10)
[1174405085] (1, 3, 5) (5, 3, 1) (9, 3, 4)
[1073741823] (3, 1, 6) (6, 1, 3)
[1073594370] (1, 9, 4)
[1064182911] (4, 3, 7) (7, 3, 4)
[1006632930] (3, 1, 10)
[714429611] (3, 1, 4) (4, 1, 3)
[713031595] (1, 7, 5) (5, 7, 1) (7, 7, 10)
[704642988] (3, 9, 10)
[626349395] (9, 5, 3)
[621455450] (2, 3, 9)
[613543351] (1, 5, 3) (3, 5, 1)
[602795529] (1, 1, 9) (7, 3, 9) (9, 1, 1) (9, 3, 7)
[536870911] (3, 5, 7) (6, 9, 7) (7, 5, 3) (7, 9, 6)
[536772612] (1, 1, 3)
[534773505] (6, 7, 1)
[528482241] (8, 3, 9)
[520093634] (1, 5, 10)
[469762041] (1, 7, 4) (4, 1, 7) (7, 1, 4)
[459276069] (4, 7, 5)
[453248985] (1, 3, 7)
[429286605] (5, 7, 6) (6, 7, 5)
[426141261] (1, 3, 8) (8, 3, 1)
[390070086] (1, 1, 6)
[389118324] (3, 3, 10)
[352321494] (6, 7, 9)
[352106517] (3, 7, 5) (5, 7, 3)
[341310837] (8, 7, 1)
[335544315] (4, 9, 7) (7, 7, 8) (7, 9, 4) (8, 7, 7)
[335360010] (3, 9, 5)
[310727725] (9, 3, 2)
[286331153] (5, 3, 8) (8, 3, 5)
[268435455] (1, 9, 3) (3, 9, 1)
[268435454] (3, 1, 8) (7, 9, 8) (8, 9, 7)
[268435452] (3, 1, 7) (7, 1, 3)
[268435448] (2, 3, 7)
[267386370] (5, 7, 7) (7, 7, 5)
[260046817] (4, 3, 1)
[259507262] (9, 5, 5)
[252645135] (3, 1, 5) (5, 1, 3)
[249690255] (5, 9, 8)
[234637326] (4, 1, 5)
[201326586] (5, 3, 6) (5, 7, 9) (6, 3, 5)
[201222147] (3, 7, 8) (8, 7, 3)
[195225786] (8, 1, 7)
[178924204] (3, 1, 1)
[167772155] (4, 3, 9)
[167680005] (5, 9, 3)
[153391689] (1, 5, 2) (2, 5, 1)
[153092023] (5, 7, 4)
[142501905] (2, 3, 5) (5, 3, 2)
[134217727] (8, 1, 3)
[134217726] (7, 5, 8)
[134150145] (3, 7, 9)
[134085633] (3, 7, 6) (6, 7, 3)
[133693185] (1, 9, 7) (7, 9, 1)
[129753631] (3, 9, 4) (4, 9, 3) (5, 5, 9)
[117318663] (5, 1, 4)
[100663293] (8, 9, 9)
[97612893] (7, 1, 8)
[97517382] (1, 7, 8)
[94371795] (1, 7, 3) (3, 7, 1)
[93323175] (6, 1, 7) (7, 1, 6)
[89478485] (3, 5, 9)
[87951402] (5, 9, 10)
[82993665] (4, 3, 5) (5, 3, 4)
[78212442] (1, 7, 10) (7, 5, 9) (9, 5, 7)
[75497463] (9, 3, 8)
[69273666] (7, 5, 1)
[67108863] (4, 7, 1) (5, 9, 9)
[67108862] (7, 3, 2)
[67084290] (9, 5, 10)
[66584449] (9, 3, 10)
[66059784] (4, 5, 9) (9, 5, 4)
[65536191] (2, 1, 5) (5, 1, 2)
[65011681] (6, 1, 1)
[62914530] (1, 7, 2) (2, 7, 1)
[58260615] (2, 9, 3) (3, 9, 2)
[57252195] (3, 5, 4) (4, 5, 3)
[56884380] (1, 1, 5) (5, 1, 1)
[55050135] (3, 1, 9) (9, 1, 3)
[47439707] (1, 5, 8) (8, 5, 1)
[44739242] (8, 5, 7)
[42105595] (1, 9, 8) (8, 9, 1)
[41287365] (5, 9, 6)
[34636833] (1, 3, 6) (1, 5, 7) (6, 3, 1)
[33554430] (3, 3, 8) (8, 3, 3)
[33554416] (6, 5, 3)
[30593745] (6, 7, 7) (7, 7, 6)
[23194290] (7, 3, 6)
[22282155] (1, 3, 2) (2, 3, 1)
[19473111] (1, 1, 4) (4, 1, 1)
[19168695] (1, 1, 8) (8, 1, 1)
[17284575] (5, 7, 8) (8, 7, 5)
[16777215] (1, 3, 3) (3, 3, 1) (5, 3, 9) (9, 3, 5)
[16777208] (3, 5, 6)
[16129169] (5, 1, 7) (7, 1, 5)
[14351946] (3, 7, 7)
[11597145] (6, 3, 7)
[11184810] (2, 7, 5) (5, 7, 2)
[11180715] (3, 7, 4) (4, 7, 3)
[9266985] (3, 3, 7) (7, 3, 3)
[8382465] (1, 1, 10)
[8257473] (6, 9, 5)
[7798308] (5, 5, 6)
[7427385] (4, 9, 9)
[7339976] (8, 1, 9) (9, 1, 8)
[5963685] (4, 9, 5) (5, 9, 4)
[5832615] (7, 1, 10)
[5592405] (2, 1, 3) (3, 1, 2)
[5374005] (5, 1, 9) (9, 1, 5)
[5332341] (7, 3, 1)
[5158440] (2, 1, 9)
[4783982] (7, 7, 3)
[3997791] (1, 9, 9)
[2936010] (5, 1, 10)
[2790571] (2, 9, 7) (7, 9, 2)
[2579220] (9, 1, 2)
[2162622] (3, 3, 5)
[2149602] (2, 1, 7) (7, 1, 2)
[1179612] (5, 5, 8) (8, 5, 5)
[1081311] (5, 3, 3)
[1048575] (1, 3, 9) (1, 5, 6) (6, 5, 1) (9, 3, 1)
[1043970] (8, 5, 3)
[1016379] (7, 9, 10)
[1003935] (6, 1, 9) (9, 1, 6)
[573405] (2, 7, 3) (3, 7, 2)
[557039] (1, 1, 7) (7, 1, 1)
[522753] (3, 3, 4) (4, 3, 3)
[521985] (3, 5, 8)
[458724] (7, 3, 8) (8, 3, 7)
[390915] (4, 5, 7) (7, 5, 4)
[278511] (6, 5, 5)
[131070] (1, 4, 7) (1, 8, 9) (1, 10, 10) (2, 4, 9) (2, 5, 6) (2, 7, 4) (2, 7, 8) (2, 7, 10) (2, 8, 7) (4, 6, 7) (4, 7, 2) (4, 9, 4) (5, 2, 9) (5, 4, 7) (5, 6, 8) (5, 8, 7) (5, 8, 10) (6, 5, 2) (6, 8, 7) (7, 4, 1) (7, 4, 5) (7, 6, 4) (7, 8, 2) (7, 8, 5) (7, 8, 6) (8, 6, 5) (8, 7, 2) (8, 7, 10) (9, 2, 5) (9, 4, 2)
[129794] (2, 5, 4) (2, 9, 8) (3, 5, 3) (4, 5, 2) (4, 5, 6) (5, 8, 9) (6, 5, 4) (8, 9, 2)
[128961] (7, 5, 10)
[126914] (6, 3, 10) (7, 6, 9) (7, 10, 9) (8, 6, 9) (9, 6, 7) (9, 6, 8)
[114674] (1, 2, 7) (1, 2, 9) (3, 4, 10) (5, 10, 7) (7, 2, 1) (7, 2, 8) (7, 10, 5) (8, 2, 7) (9, 2, 1)
[110670] (3, 2, 5) (5, 2, 3)
[98301] (4, 7, 7) (7, 7, 4)
[95046] (4, 4, 7) (5, 2, 2) (5, 6, 10) (7, 4, 4)
[85974] (2, 4, 7) (6, 6, 1) (7, 4, 2)
[65535] (2, 10, 4) (4, 10, 2) (5, 7, 10)
[65534] (1, 3, 1) (1, 6, 5) (3, 4, 9) (3, 10, 5) (4, 7, 4) (5, 6, 1) (5, 6, 7) (5, 10, 3) (6, 3, 8) (7, 6, 5) (8, 3, 6) (9, 4, 3)
[65532] (4, 10, 3)
[65528] (1, 2, 3) (4, 5, 10) (7, 4, 9) (9, 4, 7)
[64770] (1, 4, 9) (9, 4, 1)
[63240] (3, 4, 4) (4, 4, 3) (8, 2, 9) (9, 2, 8)
[61410] (2, 2, 7) (7, 2, 2)
[61320] (9, 2, 10)
[57316] (2, 3, 2) (6, 5, 8) (8, 5, 6)
[57288] (3, 8, 7) (7, 8, 3)
[55335] (4, 2, 6) (6, 2, 4) (8, 7, 9)
[55118] (3, 8, 8) (8, 8, 3)
[49146] (1, 8, 7) (2, 3, 8) (3, 4, 5) (5, 4, 3) (7, 8, 1) (8, 3, 2)
[47523] (2, 2, 8) (8, 2, 2)
[47244] (4, 7, 6) (6, 7, 4) (6, 10, 9)
[43690] (1, 2, 5) (1, 10, 3) (3, 10, 1) (3, 10, 7) (5, 2, 1) (5, 4, 6) (6, 4, 5) (7, 2, 9) (7, 8, 8) (7, 10, 3) (8, 8, 7) (9, 2, 7) (9, 4, 10)
[42966] (1, 8, 3) (2, 8, 5) (3, 8, 1) (3, 8, 5) (5, 8, 2) (5, 8, 3) (6, 7, 10)
[40955] (3, 9, 8) (8, 9, 3)
[39370] (5, 2, 6) (6, 2, 5)
[32767] (2, 2, 6) (6, 2, 2)
[32766] (2, 3, 6) (2, 9, 10) (2, 10, 9) (3, 2, 9) (3, 8, 6) (3, 10, 4) (3, 10, 10) (4, 4, 5) (4, 7, 10) (4, 9, 10) (5, 4, 4) (6, 3, 2) (6, 8, 3) (9, 2, 3)
[32764] (3, 2, 1)
[32752] (2, 6, 7) (4, 8, 5) (5, 8, 4) (7, 6, 2)
[31682] (2, 2, 5)
[31248] (6, 6, 5)
[30660] (3, 7, 3)
[28658] (1, 6, 6) (5, 4, 8) (8, 4, 5) (8, 10, 6)
[28644] (3, 2, 10)
[26670] (2, 10, 3) (3, 10, 2) (5, 10, 8) (8, 10, 5)
[26214] (2, 2, 9) (2, 9, 4) (4, 9, 2) (9, 2, 2)
[26040] (2, 8, 3)
[24573] (2, 6, 10)
[24528] (2, 5, 10) (5, 3, 5)
[23622] (7, 6, 1)
[22134] (3, 8, 4) (4, 8, 3)
[21844] (3, 2, 4) (4, 2, 3)
[21590] (3, 10, 9)
[21483] (4, 6, 6) (6, 6, 4)
[21420] (5, 2, 8) (8, 2, 5)
[21336] (1, 10, 9)
[20470] (7, 10, 10) (8, 10, 9)
[20460] (7, 8, 9)
[16383] (4, 6, 10) (4, 10, 10)
[16002] (5, 10, 6) (6, 10, 5)
[15810] (3, 5, 10)
[15748] (1, 6, 7)
[15624] (5, 6, 6)
[15330] (1, 4, 10) (3, 10, 6) (4, 9, 6) (6, 9, 4) (6, 10, 3)
[14329] (6, 10, 8)
[14322] (2, 10, 10) (3, 6, 10) (4, 3, 6) (4, 6, 9) (6, 3, 4) (9, 6, 4) (9, 6, 10)
[14280] (8, 6, 10)
[13020] (3, 8, 2)
[10922] (2, 4, 5) (5, 4, 2)
[10710] (6, 6, 7) (7, 6, 6)
[10668] (2, 10, 8)
[10416] (4, 3, 4)
[10230] (1, 5, 1)
[9362] (1, 4, 6) (2, 3, 4) (3, 6, 7) (3, 10, 8) (4, 3, 2) (6, 4, 1) (6, 9, 8) (7, 6, 3) (8, 9, 6) (8, 10, 3)
[9198] (3, 2, 6) (4, 10, 7) (6, 2, 3) (7, 10, 4)
[9052] (2, 8, 9)
[8190] (1, 6, 10) (1, 10, 6) (2, 6, 9) (4, 3, 10) (5, 4, 10) (5, 8, 6) (6, 4, 7) (6, 8, 5) (6, 10, 1) (6, 10, 7) (7, 2, 10) (7, 4, 6) (7, 10, 6) (9, 6, 2)
[8184] (4, 2, 5) (5, 4, 9) (7, 6, 7) (9, 4, 5)
[7905] (8, 6, 2)
[7710] (2, 10, 7) (7, 10, 2)
[7140] (6, 2, 9) (9, 2, 6)
[7112] (5, 8, 1)
[6510] (6, 10, 10)
[5460] (3, 8, 10)
[5334] (1, 10, 5) (5, 10, 1) (6, 8, 9)
[5208] (3, 2, 7)
[4774] (1, 2, 10)
[4526] (4, 10, 6)
[4284] (8, 3, 10)
[4095] (6, 2, 10) (7, 2, 7)
[4094] (2, 2, 10)
[4092] (3, 2, 8) (5, 2, 4) (7, 10, 7) (8, 2, 3)
[4088] (8, 8, 9)
[3906] (4, 10, 9)
[3810] (3, 6, 8) (8, 6, 3)
[3556] (2, 5, 2) (9, 2, 9)
[3472] (2, 6, 3) (3, 6, 2)
[3276] (1, 4, 3) (3, 4, 1)
[3069] (3, 10, 3) (5, 6, 5)
[3066] (7, 8, 10)
[2920] (2, 5, 8) (8, 5, 2)
[2730] (1, 8, 10) (5, 2, 7) (6, 10, 2) (7, 2, 5) (7, 6, 10)
[2570] (4, 8, 9)
[2520] (4, 8, 7) (7, 8, 4)
[2286] (1, 6, 9) (9, 6, 1)
[2263] (6, 10, 4)
[2142] (1, 10, 7) (2, 4, 3) (3, 4, 2) (7, 10, 1)
[2114] (3, 4, 7) (7, 4, 3)
[2044] (6, 5, 10)
[1953] (3, 6, 3) (3, 9, 3) (6, 6, 8) (6, 9, 6) (8, 6, 6)
[1778] (1, 8, 5)
[1533] (3, 9, 9) (6, 6, 10) (9, 6, 3)
[1530] (3, 4, 6) (5, 2, 10) (6, 4, 3)
[1524] (2, 2, 3) (3, 2, 2) (7, 10, 8)
[1365] (1, 10, 1) (2, 10, 6) (5, 2, 5)
[1302] (3, 6, 5) (5, 6, 3) (7, 2, 3) (8, 2, 6)
[1190] (2, 6, 4) (4, 6, 2)
[1116] (5, 10, 9)
[1068] (3, 4, 8) (8, 4, 3)
[1023] (3, 3, 6) (6, 3, 3)
[1022] (8, 2, 10)
[1020] (4, 4, 9) (4, 10, 5) (5, 8, 8) (5, 10, 4) (6, 2, 7) (7, 2, 6) (8, 8, 5) (9, 4, 4)
[1008] (1, 2, 6) (6, 2, 1)
[930] (3, 6, 4) (4, 2, 7) (4, 6, 3) (7, 2, 4)
[889] (8, 10, 2)
[868] (1, 6, 2) (1, 10, 4) (2, 6, 1) (4, 2, 9) (4, 10, 1) (9, 2, 4)
[840] (8, 6, 7)
[762] (1, 4, 5) (5, 4, 1) (8, 10, 7)
[682] (7, 4, 10)
[630] (1, 6, 3) (2, 3, 10) (3, 6, 1) (5, 6, 9) (6, 4, 9) (9, 4, 6) (9, 6, 5)
[511] (3, 6, 9)
[510] (2, 6, 5) (2, 6, 8) (2, 8, 10) (2, 9, 6) (3, 8, 9) (4, 6, 5) (5, 6, 2) (5, 6, 4) (6, 9, 2)
[508] (1, 2, 2) (1, 10, 8) (2, 2, 1) (4, 3, 8) (4, 9, 8) (6, 7, 8) (6, 9, 9) (8, 3, 4) (8, 7, 6) (8, 9, 4) (8, 10, 1) (9, 3, 9)
[496] (1, 2, 8) (8, 2, 1)
[476] (2, 7, 6) (6, 7, 2)
[434] (6, 2, 8)
[420] (7, 6, 8)
[315] (8, 10, 10)
[280] (8, 5, 10)
[255] (4, 4, 8) (8, 4, 4)
[254] (3, 8, 3) (4, 4, 10) (4, 6, 4) (4, 10, 8) (6, 8, 10) (8, 10, 4)
[252] (1, 7, 1) (1, 10, 2) (2, 7, 2) (2, 10, 1) (4, 8, 10) (6, 4, 10) (7, 3, 7) (8, 8, 10) (8, 9, 10)
[248] (4, 6, 8) (6, 6, 9) (9, 6, 6)
[240] (1, 2, 4) (4, 2, 1)
[234] (4, 5, 8) (8, 5, 4)
[210] (1, 8, 6) (2, 6, 6) (6, 6, 2) (6, 8, 1)
[186] (2, 8, 6) (2, 10, 2) (5, 4, 5) (6, 8, 2)
[170] (3, 3, 9)
[146] (3, 6, 6) (6, 6, 3)
[127] (6, 9, 3)
[126] (6, 4, 8) (7, 4, 7) (7, 4, 8) (8, 4, 6) (8, 4, 7)
[124] (8, 6, 4)
[120] (1, 4, 8) (1, 6, 4) (1, 6, 8) (4, 6, 1) (5, 7, 5) (5, 9, 5) (6, 5, 6) (6, 7, 6) (8, 4, 1) (8, 6, 1) (9, 6, 9)
[105] (5, 10, 10)
[102] (4, 8, 6) (6, 8, 4) (6, 8, 8) (6, 9, 10) (8, 8, 6)
[93] (1, 6, 1) (3, 2, 3) (6, 3, 6)
[85] (4, 2, 10) (9, 3, 3)
[84] (2, 4, 6) (2, 6, 2) (2, 10, 5) (3, 4, 3) (5, 10, 2) (6, 4, 2) (8, 4, 10)
[63] (6, 4, 6)
[60] (2, 4, 4) (2, 4, 8) (4, 4, 2) (4, 10, 4) (5, 8, 5) (8, 4, 2)
[56] (1, 4, 4) (4, 4, 1)
[51] (6, 3, 9) (9, 3, 6)
[48] (4, 4, 6) (4, 7, 8) (6, 4, 4) (8, 7, 4)
[42] (2, 4, 10) (5, 5, 10)
[35] (5, 5, 5)
[32] (1, 1, 1) (1, 4, 2) (1, 8, 2) (1, 8, 4) (1, 9, 1) (2, 1, 2) (2, 1, 4) (2, 1, 6) (2, 1, 8) (2, 1, 10) (2, 4, 1) (2, 8, 1) (2, 9, 2) (3, 1, 3) (4, 1, 2) (4, 1, 4) (4, 1, 6) (4, 1, 8) (4, 1, 10) (4, 5, 4) (4, 8, 1) (5, 1, 5) (6, 1, 2) (6, 1, 4) (6, 1, 6) (6, 1, 8) (6, 1, 10) (7, 1, 7) (7, 5, 7) (7, 9, 7) (8, 1, 2) (8, 1, 4) (8, 1, 6) (8, 1, 8) (8, 1, 10) (8, 3, 8) (8, 4, 9) (8, 5, 8) (9, 1, 9) (9, 4, 8) (9, 5, 9)
[31] (1, 2, 1) (3, 3, 3) (7, 7, 7)
[30] (6, 8, 6)
[24] (2, 8, 8)
[21] (2, 2, 4) (4, 2, 2)
[16] (1, 4, 1) (1, 8, 1) (1, 8, 8) (2, 2, 2) (4, 2, 8) (6, 2, 6) (6, 10, 6) (8, 2, 4) (8, 2, 8) (8, 8, 1) (9, 4, 9)
[15] (2, 4, 2)
[14] (6, 6, 6)
[12] (4, 8, 8) (8, 8, 2) (8, 8, 4)
[8] (2, 8, 2) (2, 8, 4) (4, 2, 4) (4, 4, 4) (4, 8, 2) (7, 8, 7) (8, 4, 8) (8, 6, 8) (8, 9, 8) (8, 10, 8)
[7] (4, 8, 4) (5, 10, 5)
[5] (3, 9, 6)
[4] (8, 7, 8)
[2] (8, 8, 8)
......5min timeout
可以看到，排在第一的恰巧是（1，3，10）周期为4294967295，正好是 232 – 1
一排多组，表示周期相等。
问题，为什么要有两次左移和一次右移呢？其实只一次左移加异或就能达到随机的效果。
猜测，之所以这样，大概是因为，第一次左移，是为了让高位多1，右移，是为了让低位多1，这样，高位低位都参与进来，增加随机性，第二次左移，便是真正的随机了。
行文至此结束。
尊重他人的劳动，转载请注明出处：http://www.cnblogs.com/aniao/p/aniao_exchanger.html
