关于在n-1的数组中找到那个被减去的数及异或与位与

浏览数：18 / 时间：2015年06月08日

// 有1到N共 n-1个数，问少了哪个数
// 有序数组(如果是无序数组那么将a[i] 移动至 a[a[i]] 这样子就成功排序了)

public static void lessOne(int[] a) {
　　int fruit = 0;
　　int count = 0;
　　for (int i = 0; i < a.length; i++) {
　　count++;
　　fruit ^= a[i];
　　if (count == 4) {
　　　　if (fruit == 0) {
　　　　　　count = 0;
　　　　} else {

　　　　System.out.println("Less is:" + i);
　　　　break;
　　　　}
　　　　}
　　}
}

下面为测试代码

int[] a = new int[100];
for (int i = 0; i < a.length; i++) {
　　if (i == 67)
　　　　continue;
　　a[i] = i;
}
//也可以使用已提供的方法进行排序，但不建议
//Arrays.sort(a);
lessOne(a);

// 有一组数，中间有两个数的出现次数为奇数次，问是哪两个数

public static void lesstwoj() {
int[] a = { 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 8 };
　　int sum = 0;
　　for (int i : a) {
　　　　sum ^= i;
　　}
　　int count = 0;
　　int temp = sum;
　　while ((temp & 1) == 0) {
　　temp >>= 1;
　　count++;
　　}
　　int one = 0;
　　for (int i : a) {
　　　　if (((i >> count) & 1) != 0) {
　　　　　　one ^= i;
　　　　}
　　}
　　int sec = sum ^ one;
　　System.out.println("one:" + one);//第一个数
　　System.out.println("sec:" + sec);//第二个数
}

// 采用异或运算来进行交换位置

//不借助于第三个数

public static void swap(int a, int b) {
　　if (a != b) {
　　　　a = a ^ b;
　　　　b = a ^ b;
　　　　a = a ^ b;
　　}
　　System.out.println("one-- a:" + a + " b:" + b);
}