output

0111
1011
0101
1010
1101
0110
0011
1001
0100
0010
0001
1000
1100
1110
1111
0111

source code

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 35 Random Numbers<br>
* Problem3<br>
* 図35.1のようなフィードバックシフトレジスタで、取り出し口の位置を先頭と最後にしたものによって生成されるパターンの系列を示せ。初期パターンは1111とする。
*/
public class Chapter35RandomNumbersProblem3 {
public static void main(String[] args) {
Chapter35RandomNumbersProblem3 o = new Chapter35RandomNumbersProblem3();
o.run();
}

private void run() {
LinearFeedbackShiftRegister3 rng = new LinearFeedbackShiftRegister3(new int[] { 1, 1, 1, 1, }, 3, 0);
for (int i = 0; i < (1 << 4); i++) {
System.out.format("%4s\n", toBinaryString(rng.nextInt()));
}
}

private String toBinaryString(int n) {
String res = "";
for (int i = 0; i < 4; i++) {
res = ((n & (1 << i)) == 0 ? "0" : "1") + res;
}
return res;
}

private class LinearFeedbackShiftRegister3 {
private int[] a;
private int n;
private int b;
private int bit;
private int j;

public LinearFeedbackShiftRegister3(int[] a, int b, int bit) {
this.a = a;
this.n = a.length;
this.b = b;
this.bit = bit;
this.j = n - 1;
}

public int nextInt() {
a[j] ^= a[(j - b + n) % n];
int res = 0;
for (int i = 0; i < n; i++) {
res += ((a[(j + i) % n] & (1 << bit)) >>> bit) * (1 << n - 1 - i);
}
j = (j - 1 + n) % n;
return res;
}
}
}