---

套路

• 涉及到二进制、不用单目运算符做加法运算，其中某一位的问题（两数不同，至少有一位不同）
• 求解运算符选择受限时可以考虑利用逻辑与&&逻辑或||的短路特性
• 二进制数1的个数： n = n & n - 1
• a ^ b 不进位加法，(a & b) << 1 进位加法
• 仅利用位去存储少量（小于32）的数字

---

注意点

• 暂无

---

目录

• 二进制中1的个数
• 求1+2+3+...+n
• 数组中只出现一次的数字
• 不用加减乘除做加法
• 扑克牌顺子

---

二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

• 解法一：将数字转二进制字符串，再处理每一个字符

public int NumberOf1(int n) {
    int ans = 0;
    char[] arr = Integer.toBinaryString(n).toCharArray();
    for (char ch : arr) {
        if (ch == '1') ans++;
    }
    return ans;
}

• 解法二： 将数字转成二进制字符串，再将其中的0用""代替，返回结果字符串的长度即可

public int NumberOf1(int n) {
    return Integer.toBinaryString(n).replaceAll("0", "").length();
}

• 最优解：位运算，n = n & n - 1 计算一次，1的个数减一

public int NumberOf1(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;
        count++;
    }
    return count;
}

---

求1+2+3+...+n

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

• 递归调用的出口不能用if语句，可用 n == 0 时 && (逻辑与)的短路特性来终止递归调用

public int Sum_Solution(int n) {
    boolean b = (n > 0) && ((n += Sum_Solution(n - 1)) > 0);
    return n;
}

---

数组中只出现一次的数字

题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

• 数组中只有出现了一次和出现了两次的数，所以可以用异或解题。出现了两次的数异或结果为0，整个数组异或完就是两个只出现一次的数异或的结果。
• 这两个数字不同，其中必然有一位一个是1，一个是0，从刚才异或的结果中找到这一位的位置。两数组按这一位为0和为1分成两部分，其中相同的数那一位必然都为0或都为1，一定会被分在一组，而两个只出现一次的数因为那一位不同，必然会被分在不同的组。两组各自分别再进行一遍异或，即可得到两个数。

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    // ans 保存两个只出现一次的数异或的结果
    // index 保存ans中不同的那一位从右往左方向的索引位置
    int ans = 0, index = 0;
    for (int i = 0; i < array.length; i++) {
        ans ^= array[i];
    }
    // == 比 & 优先级高！
    while ((ans & 1) == 0) {
        ans >>= 1;
        index++;
    }
    for (int i = 0; i < array.length; i++) {
        // == 比 & 优先级高！
       (array[i] >> index & 1) == 0 ? num1[0] ^= array[i] : num2[0] ^= array[i];
    }
}

---

不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

• a ^ b 不进位加法，(a & b) << 1 进位加法,两者之和为不进位加法结果加进位加法相加的结果，然而不能用+号得到。我们不断的循环调用这一过程，当进位加法为0时，不进位加法的结果即为两数之和。

public int Add(int num1,int num2) {
    do {
        int temp = num1 ^ num2;
        num2 = (num1 & num2) << 1;
        num1 = temp;
    } while (num2 != 0);
    return num1;
}

---

扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

• 最优解：不使用任何额外空间（一两个变量不算啊，空间在这里指数据结构），时间复杂度 O(n)，只要满足以下两条即可： 1. 除0以外没有重复的数；2. 除0以外其它数的差小于5。因为数字最大值只有13，所以可以用以下这种方式保存数字，数字1左移num位保存在bitFlag里，标记出现过的数字用来判重。

public boolean isContinuous(int [] numbers) {
    if (numbers == null || numbers.length != 5) {
        return false;
    }
    int min = 14, max = -1, bitFlag = 0;
    for (int i = 0; i < 5; i++) {
        int num = numbers[i];
        if (num < 0 || num > 13) return false;
        if (num == 0) continue;
        if ((bitFlag >> num & 1) == 1) return false;
        bitFlag |= 1 << num;
        if (num < min) min = num;
        if (num > max) max = num;
        if (max - min >= 5) return false;
    }
    return true;
}

---