数字的位操作——326、504、263、190、191、476、461、477、693

326. 3 的幂（简单）

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：
输入：n = 27
输出：true
示例 2：
输入：n = 0
输出：false
示例 3：
输入：n = 9
输出：true
示例 4：
输入：n = 45
输出：false
提示：

-231 <= n <= 231 - 1

解法一、同余数

int范围内3的幂最大是3^19。这个方法可以解所有x的幂的问题

class Solution {public boolean isPowerOfThree(int n) {int b = (int)Math.pow(3,19);return n > 0 && b % n == 0?true:false;}
}

解法二、循环除三

class Solution {public boolean isPowerOfThree(int n) {while (n != 0 && n % 3 == 0) {n /= 3;}return n == 1;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/power-of-three/solutions/1011809/3de-mi-by-leetcode-solution-hnap/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

504. 七进制数（简单）

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

示例 1:
输入: num = 100
输出: "202"
示例 2:
输入: num = -7
输出: "-10"
提示：

-10^7 <= num <= 10^7

解法一、 api

class Solution {public String convertToBase7(int num) {return Integer.toString(num,7);}
}

解法二、直接算

先取余再除，记得翻转

class Solution {public String convertToBase7(int num) {if (num == 0) return "0";StringBuilder sb = new StringBuilder();int n = Math.abs(num);while (n > 0) {sb.append(n % 7);n /= 7;}if (num < 0) sb.append("-");return sb.reverse().toString();}
}

263. 丑数(简单)

简单

相关标签

相关企业

丑数就是只包含质因数 2、3 和 5 的正整数。

给你一个整数 n ，请你判断 n 是否为丑数。如果是，返回 true ；否则，返回 false 。

示例 1：
输入：n = 6
输出：true
解释：6 = 2 × 3
示例 2：
输入：n = 1
输出：true
解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。
示例 3：
输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。
提示：

-2^31 <= n <= 2^31 - 1

解法一、循环连除

第一次用do-while结构

class Solution {public boolean isUgly(int n) {int pre;do{pre = n;if(n%2 == 0)n/=2;if(n%3 == 0)n/=3;if(n%5 == 0)n/=5;}while(n != pre);return n==1?true:false;}
}

190. 颠倒二进制位（简单）

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

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：
输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596， 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
提示：

输入是一个长度为 32 的二进制字符串

进阶: 如果多次调用这个函数，你将如何优化你的算法？

解法一、API

public class Solution {// you need treat n as an unsigned valuepublic static int reverseBits(int n) {return Integer.reverse(n);}
}

解法二、模拟

+=也可以是|=（rev = rev | xxxx）因为rev那一位一定是0，两个没有差别

>>算术右移（该补1补1该补0补0）>>>逻辑右移（高位全补0）

 public class Solution {public int reverseBits(int n) {int rev = 0;for (int i = 0; i < 32 && n != 0; ++i) {rev += (n & 1) << (31 - i);n >>>= 1;}return rev;}
}

解法三、分治

M1/2/3/4相当于选中当前位。例如，对于12345678

第一行：|左面逻辑右移一位，选中奇数，变成01030507,右面先选中奇数再左移，变成20406080,拼起来变成21436587（实际操作中这里都是1，为了方便改成了十进制数）

第二行：|左面逻辑右移两位，选中每四位低两格，变成00210065，右面先选中再左移，变成43008700，拼起来变成43218765

第三行：|左面逻辑右移四位，选中每八位低四格，变成00004321，右面先选中再左移，变成87650000，拼起来变成87654321

第四行同上。先局部，再整体。

public class Solution {private static final int M1 = 0x55555555; // 01010101010101010101010101010101private static final int M2 = 0x33333333; // 00110011001100110011001100110011private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111public int reverseBits(int n) {n = n >>> 1 & M1 | (n & M1) << 1;n = n >>> 2 & M2 | (n & M2) << 2;n = n >>> 4 & M4 | (n & M4) << 4;n = n >>> 8 & M8 | (n & M8) << 8;return n >>> 16 | n << 16;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/reverse-bits/solutions/685436/dian-dao-er-jin-zhi-wei-by-leetcode-solu-yhxz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

191. 位1的个数（简单）

编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中

设置位
的个数（也被称为汉明重量）。

示例 1：
输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。
示例 2：
输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。
示例 3：
输入：n = 2147483645
输出：30
解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。
提示：

1 <= n <= 23^1 - 1

进阶：

如果多次调用这个函数，你将如何优化你的算法？

解法一、直接模拟

class Solution {public int hammingWeight(int n) {String a = Integer.toBinaryString(n);int sum = 0;for(int i = 0;i < a.length();i++){if(a.charAt(i) == '1')sum++;}return sum;}
}

解法二、模拟

不必转，可以直接用检验方法在原数字上面做计算

public class Solution {public int hammingWeight(int n) {int ret = 0;for (int i = 0; i < 32; i++) {if ((n & (1 << i)) != 0) {ret++;}}return ret;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/number-of-1-bits/solutions/672082/wei-1de-ge-shu-by-leetcode-solution-jnwf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法三、解法二优化

n&(n-1)可以把最后一个1去掉

备注：n&-n==n代表n是2的幂

public class Solution {public int hammingWeight(int n) {int ret = 0;while (n != 0) {n &= n - 1;ret++;}return ret;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/number-of-1-bits/solutions/672082/wei-1de-ge-shu-by-leetcode-solution-jnwf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

476. 数字的补数（简单）

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

给你一个整数 num ，输出它的补数。

示例 1：
输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
示例 2：
输入：num = 1
输出：0
解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
提示：

1 <= num < 231

注意：本题与 1009 . - 力扣（LeetCode）相同

解法一、位运算

可见5+2+1 = 8 = 2^3。取到最高位，然后左移一位，然后相减减一即可。

class Solution {public static int findComplement(int num) {int n = Integer.highestOneBit(num);int res = n<<1;return res - num - 1;}
}

解法二、补一取反

操作后会从0000100变成1111100，补完取反则0000011

class Solution {
public:int findComplement(uint num) {uint t = 1u << 31;//左移31位的无符号1while (! (t & num)) {//条件：只要t与num是0num |= t;//num补1t >>= 1;//t左移}return ~num;}
};

解法三、异或

如对100，while后p变成111，异或后变成011

   int findComplement(int num) {//位运算unsigned int p = 1;while (p < num) p <<= 1, p++;return num^p;}

461. 汉明距离(简单)

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：
输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)↑   ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：
输入：x = 3, y = 1
输出：1
提示：

0 <= x, y <= 2^31 - 1

解法一、异或

x异或y，可以留下所有不一样的位数。然后按照191.位1的个数统计总数就可以

class Solution {public static int hammingDistance(int x, int y) {int z = x^y,sum = 0;while(z != 0){z&=(z-1);sum++;}return sum;}
}

解法二、API

class Solution {public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y);}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/hamming-distance/solutions/797339/yi-ming-ju-chi-by-leetcode-solution-u1w7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

477. 汉明距离总和（中等）

两个整数的汉明距离指的是这两个数字的二进制数对应位不同的数量。

给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。

示例 1：
输入：nums = [4,14,2]
输出：6
解释：在二进制表示中，4 表示为 0100 ，14 表示为 1110 ，2表示为 0010 。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6
示例 2：
输入：nums = [4,14,4]
输出：4
提示：

1 <= nums.length <= 104
0 <= nums[i] <= 109
给定输入的对应答案符合 32-bit 整数范围

解法一、用461的轮子

知道不是最优解，但没想到这么不是

class Solution {public int totalHammingDistance(int[] nums) {int num = nums.length;int sum = 0;for(int i = 0;i < num;i++){for(int j = i+1;j < num;j++){sum+=hammingDistance(nums[i],nums[j]);}}return sum;}private int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y);}
}

解法二、纵向遍历

在计算汉明距离时，我们考虑的是同一比特位上的值是否不同，而不同比特位之间是互不影响的。

对于数组 nums 中的某个元素 val，若其二进制的第 i 位为 1，我们只需统计 nums 中有多少元素的第 i 位为 0，即计算出了 val 与其他元素在第 i 位上的汉明距离之和。

具体地，若长度为 n 的数组 nums 的所有元素二进制的第 i 位共有 c 个 1，n−c 个 0，则些元素在二进制的第 i 位上的汉明距离之和为

c⋅(n−c)
我们可以从二进制的最低位到最高位，逐位统计汉明距离。将每一位上得到的汉明距离累加即为答案。

具体实现时，对于整数 val 二进制的第 i 位，我们可以用代码 (val >> i) & 1 来取出其第 i 位的值。此外，由于 10^9<2^30 ，我们可以直接从二进制的第 0 位枚举到第 29 位。

作者：力扣官方题解
链接：https://leetcode.cn/problems/total-hamming-distance/solutions/798048/yi-ming-ju-chi-zong-he-by-leetcode-solut-t0ev/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {public int totalHammingDistance(int[] nums) {int ans = 0, n = nums.length;for (int i = 0; i < 30; ++i) {int c = 0;for (int val : nums) {c += (val >> i) & 1;}ans += c * (n - c);}return ans;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/total-hamming-distance/solutions/798048/yi-ming-ju-chi-zong-he-by-leetcode-solut-t0ev/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

693. 交替位二进制数（简单）

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：
输入：n = 5
输出：true
解释：5 的二进制表示是：101
示例 2：
输入：n = 7
输出：false
解释：7 的二进制表示是：111.
示例 3：
输入：n = 11
输出：false
解释：11 的二进制表示是：1011.
提示：

1 <= n <= 2^31 - 1

解法一、逐位检测变幻

先把flag设为最底层，之后逐个变幻flag（三目很好改）逻辑右移的方式是通过477学会的

class Solution {public boolean hasAlternatingBits(int n) {int flag = 1 & n;while (n > 0){if((n & 1) != flag)return false;n >>>=1;flag = flag == 1 ? 0 : 1;}return true;}
}

解法二、异或

如果n是按位变化，把它右移一位，和原来异或，得到的a一定全是1。那么a与a+1与运算，得到的都是0

class Solution {public boolean hasAlternatingBits(int n) {int a = n ^ (n >> 1);return (a & (a + 1)) == 0;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-number-with-alternating-bits/solutions/1368822/jiao-ti-wei-er-jin-zhi-shu-by-leetcode-s-bmxd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法三、你说得对，但我选择打表

        return n in {1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922,21845, 43690, 87381, 174762, 349525, 699050, 1398101, 2796202, 5592405,11184810, 22369621, 44739242, 89478485, 178956970, 357913941, 715827882,1431655765}