JAVA版位图排序（算法珠玑开篇的例子）

package com.sdo.tradinghub.domain;</p> <p>public class BitSortTest {<br /> private static final int BITSPERWORD = 32; // 整数位数<br /> private static final int SHIFT = 5;<br /> private static final int MASK = 0x1F; // 5位遮蔽 0B11111<br /> private static final int N = 10000000;<br /> // 用int数组来模拟位数组，总计(1 + N / BITSPERWORD)*BITSPERWORD位，足以容纳N<br /> private static int[] a = new int[(1 + N / BITSPERWORD)];</p> <p> public static void main(String[] args) {<br /> bitsort(new int[] { 1, 100, 2, 10000, 9999, 4567, 78902 });<br /> }</p> <p> public static void bitsort(int[] array) {<br /> for (int i = 0; i < N; i++)<br /> clr(i); // 位数组所有位清0<br /> for (int i = 0; i < array.length; i++)<br /> set(array[i]); // 阶段2<br /> for (int i = 0; i < N; i++)<br /> if (test(i))<br /> System.out.println(i);<br /> }</p> <p> // 置a[i>>SHIFT]的第(i & MASK)位为1，也就是位数组的第i位为1<br /> public static void set(int i) {<br /> a[i >> SHIFT] |= (1 << (i & MASK));<br /> }</p> <p> // 置a[i>>SHIFT]的第(i & MASK)位为0,也就是位数组的第i位为0<br /> public static void clr(int i) {<br /> a[i >> SHIFT] &= ~(1 << (i & MASK));<br /> }</p> <p> // 测试位数组的第i位是否为1<br /> public static boolean test(int i) {<br /> return (a[i >> SHIFT] & (1 << (i & MASK))) == (1 << (i & MASK));<br /> }<br />}