位运算

不用额外变量交换两个整数的值

package bitop;

/**
 * 不用额外变量交换两个整数的值
 * @author z8g
 */
public class SwapIntegerValue {
    public static void main(String[] args) {
        int a = 10;
        int b = -20;

        a ^= b;
        b ^= a;
        a ^= b;

        System.out.println(a + " " + b); // -20 10
    }
}

不用任何比较找出两个数中较大的数

package bitop;

/**
 * 不用任何比较找出两个数中较大的数
 *
 * @author z8g
 */
public class FindMaxNumber {

    public static void main(String[] args) {
        FindMaxNumber s = new FindMaxNumber();
        System.out.println(s.max(-1, -2));  // -1
        System.out.println(s.max(2, -2));  // 2
    }

    // 如果a-b的值为正数或0，则sign为0，flip为1，返回b
    public int max(int a, int b) {
        int remaining = a - b;
        int sign = sign(remaining);
        int flip = flip(sign);
        return a * sign + b * flip;
    }

    // 整数和0返回1，负数返回0
    private int sign(int n) {
        return flip((n >> 31) & 1);
    }

    // 如果n为1，返回0；如果n为0，返回1
    private int flip(int n) {
        return n ^ 1;
    }
}

整数的二进制表达中有多少个1

package bitop;

/**
 * 整数的二进制表达中有多少个1
 *
 * @author z8g
 */
public class IntegerNumberOf1 {

    public int numberOf1(int n) {
        int res = 0;
        while (n != 0) {
            n -= n & (~n + 1); // n & (~n + 1) 用于得到最右边的1
            res++;
        }
        return res;
    }
}

找出数组中出现次数为奇数次的数

package bitop;

import java.util.Arrays;

/**
 * 找出数组中出现次数为奇数次的数
 *
 * @author z8g
 */
public class FindNumberInArray {

    public static void main(String[] args) {
        FindNumberInArray s = new FindNumberInArray();
        int[] arr1 = {1, 2, 2, 3, 3, 4, 4, 4, 4};
        System.out.println(s.find1(arr1));

        int[] arr2 = {1, 2, 3, 3, 4, 4, 4, 4};
        System.out.println(Arrays.toString(s.find2(arr2)));
    }

    // 有一种数出现了奇数次
    public int find1(int[] arr) {
        int n = 0;
        for (int i = 0; i < arr.length; i++) {
            n ^= arr[i];
        }
        return n;
    }

    // 有两种数出现了奇数次
    public int[] find2(int[] arr) {
        int n = find1(arr); // n = a ^ b
        int rightOne = n & (~n + 1);
        int eOhasOne = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & rightOne) != 0) {
                eOhasOne ^= arr[i];
            }
        }
        return new int[]{eOhasOne, (n ^ rightOne)};
    }
}