Men的博客

欢迎光临！

0%

位运算

发表于

异或求或

二进制中1的个数

public int hammingWeight(int n) {
    int bits = 0;
    int mask = 1;
    for (int i = 0; i < 32; i++) {
        if ((n & mask) != 0) {
            bits++;
        }
        mask <<= 1;
    }
    return bits;
}
方法 2：位操作的小技巧
我们可以把前面的算法进行优化。我们不再检查数字的每一个位，而是不断把数字最后一个 1 反转，并把答案加一。当数字变成 
0 的时候偶，我们就知道它没有 1 的位了，此时返回答案

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

数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次
的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
方法一：分组异或
class Solution {
    public int[] singleNumbers(int[] nums) {
        //用于将所有的数异或起来
        int k = 0;
    
    for(int num: nums) {
        k ^= num;
    }
    
    //获得k中最低位的1
    int mask = 1;

    //mask = k & (-k) 这种方法也可以得到mask，具体原因百度 哈哈哈哈哈
    while((k & mask) == 0) {
        mask <<= 1;
    }
    
    int a = 0;
    int b = 0;
    
    for(int num: nums) {
        if((num & mask) == 0) {
            a ^= num;
        } else {
            b ^= num;
        }
    }
    
    return new int[]{a, b};
}

}

圆圈中最后剩下的数字 约瑟夫环问题

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个
数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数
字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
Java解决约瑟夫环问题，告诉你为什么模拟会超时！
总结一下反推的过程，就是 (当前index + m) % 上一轮剩余数字的个数。
class Solution {
    public int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
}

不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

缺失的第一个正数

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
方法一：排序
class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);

    // 判断 n 是否出现在末位
    if (nums[nums.length-1] != nums.length) {
        return nums.length;
    }
    // 判断 0 是否出现在首位
    else if (nums[0] != 0) {
        return 0;
    }

    // 此时缺失的数字一定在 (0, n) 中
    for (int i = 1; i < nums.length; i++) {
        int expectedNum = nums[i-1] + 1;
        if (nums[i] != expectedNum) {
            return expectedNum;
        }
    }

    // 未缺失任何数字（保证函数有返回值）
    return -1;
}
}
方法二：哈希表
class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for (int num : nums) numSet.add(num);

    int expectedNumCount = nums.length + 1;
    for (int number = 0; number < expectedNumCount; number++) {
        if (!numSet.contains(number)) {
            return number;
        }
    }
    return -1;
}
}
方法三：位运算
class Solution {
    public int missingNumber(int[] nums) {
        int missing = nums.length;
        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }
}
方法四：数学
我们可以用 高斯求和公式 求出 [0..n] 的和，减去数组中所有数的和，就得到了缺失的数字。高斯求和公式即
class Solution {
    public int missingNumber(int[] nums) {
        int expectedSum = nums.length*(nums.length + 1)/2;
        int actualSum = 0;
        for (int num : nums) actualSum += num;
        return expectedSum - actualSum;
    }
}

判断一个数是不是2的指数

一个数如果是2的指数，那么他的二进制表示中一定y只含有一个1
2^0 = 1 = 0b0001;
2^1 = 2 = 0b0010;

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

方法一：循环迭代
public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) {
            return false;
        }

    while (n % 3 == 0) {
        n /= 3;
    }

    return n == 1;
}
}
方法二：基准转换
我们所要做的就是将数字转换为以3为底的基数 ，并检查它是否为前导1，后跟所有 0
public class Solution {
    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }
}
方法三：运算法
public class Solution {
    public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}
方法四：整数限制
 n 的类型是 int 在 Java 中说明了该变量是四个字节，他的最大值为 2147483647
我们现在可以推断出 n 的最大值，也就是 3 的幂，是 1162261467
因此我们只需要将 3的19次方  除以 n。若余数为 0 意味着 n 是 的除数，因此是 3 的幂
public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

给定一个Excel表格中的列名称，返回其相应的列序号。

    本质就是26进制呗
    A -> 1
        B -> 2
        C -> 3
    AA -> 27
        AB -> 28 
    class Solution {
        public int titleToNumber(String s) {
            int ans = 0;
            for(int i=0;i<s.length();i++) {
                int num = s.charAt(i) - 'A' + 1;
                ans = ans * 26 + num;
            }
            return ans;
        }
    }

阶乘后的零

    方法1:一步一步的乘
    方法2:因子5，看有多少对 5 的因子。
    public int trailingZeroes(int n) {
            
        // Calculate n!
            BigInteger nFactorial = BigInteger.ONE;
            for (int i = 2; i <= n; i++) {
                nFactorial = nFactorial.multiply(BigInteger.valueOf(i));
            }
                            
            // Count how many 0's are on the end.
            int zeroCount = 0;
            
            while (nFactorial.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
                nFactorial = nFactorial.divide(BigInteger.TEN);
                zeroCount++;
            }
            
            return zeroCount;
            
    }

颠倒给定的 32 位无符号整数的二进制位。

    输入: 00000010100101000001111010011100
    输出: 00111001011110000010100101000000
    解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
         因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
    解法1 取模求和
    public class Solution {
        // you need treat n as an unsigned value
        public int reverseBits(int n) {
            int res = 0;
            for (int i = 0; i < 32; i++) {
                res = (res << 1) + (n & 1);
                n >>= 1;
            }
            return res;
        }
    }
    解法2 按位翻转
    public class Solution {
        // you need treat n as an unsigned value
        public int reverseBits(int n) {
            int res = 0;
            for (int i = 0; i <= 31; i++) {            
                // res += (n & (1 << i)) != 0 ? 1 << (31 - i) : 0;
                // res |= (n & (1 << i)) != 0 ? 1 << (31 - i) : 0;
                res ^= (n & (1 << i)) != 0 ? 1 << (31 - i) : 0;
            }
            return res;
        }
    }
    解法3:分治合并
    既然知道 int 值一共32位，那么可以采用分治思想，反转左右16位，然后反转每个16位中的左右8位，依次类推，最后反转2位，反转后合并即可，同时可以利用位运算在原地反转。
    public class Solution {
        // you need treat n as an unsigned value
        public int reverseBits(int n) {
            n = (n >>> 16) | (n << 16); 
            n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8); 
            n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4); 
            n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2); 
            n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1); 
            return n;
        }
    }

汉明重量

    编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
    输入：00000000000000000000000000001011
    输出：3
    解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
    方法 1：循环和位移动
    public int hammingWeight(int n) {
        int bits = 0;
        int mask = 1;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) {
                bits++;
            }
            mask <<= 1;
        }
        return bits;
    }
    方法 2：位操作的小技巧
    我们可以把前面的算法进行优化。我们不再检查数字的每一个位，而是不断把数字最后一个 1 反转，并把答案加一。当数字变成 
    0 的时候偶，我们就知道它没有 1 的位了，此时返回答案

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

统计所有小于非负整数 n 的质数的数量。

    输入: 10
    输出: 4
    解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

    int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        for (int i = 2; i * i < n; i++) 
            if (isPrim[i]) 
                for (int j = i * i; j < n; j += i) 
                    isPrim[j] = false;
    
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;
    
    return count;
    }

两数交换

1.给两个int a, b不用temp将数值调换；
int a= 1, b = 2;
a ^=b;
b^ = a;
a^ = b;

利用或|操作大写转小写

('a' | ' ') = 'a'
('A'|' ') ='a'

利用与&操作和下划线转大写

('b' & '_') = 'B'

利用异或^和空格进行大小写互换

‘d’ ^ ' ' = 'D'
'D' ^ ' ' = 'd'

判断两个数是否异或

int x = -1,y = 2;
bool  f = ((x ^ y) < 0) // true

加一

n = -~n;

减一

n = ~-n;

消除数字n的二进制表示的最后一个1

n&(n-1)