LeetCode算法题-Reverse Bits(Java实现)
这是悦乐书的第185次更新,第187篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第44题(顺位题号是190)。给定32位无符号整数,求它的反转位。例如:
输入:43261596
输出:964176192
说明:43261596以二进制表示为00000010100101000001111010011100,
964176192以二进制表示为00111001011110000010100101000000。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
既然是做位运算,那么依次将原数从左往右移动一位,取出移动的位判断是0还是1,然后加到反转的结果上,并且反转的结果是从右往左移动一位,循环控制的次数为32次,因为是32位整数。
其中涉及到左移、右移、与(&)运算,与(&)运算的规则是相同的位上均为1时结果为1,否则结果为0,而左移、右移的规则就是从右往左补0和从左往右补0了。
public int reverseBits(int n) {
int result = 0;
for (int i=0; i<32; i++) {
if ((n & 1) == 1) {
result = (result << 1) + 1;
} else {
result = result << 1;
}
n = n >> 1;
}
return result;
}
03 第二种解法
可以将上面的步骤再简化下,进入循环时,无论原数右移出来的位是0还是1,都需要结果值左移一位,对此我们可以进行或(|)运算操作。
先将结果值左移一位,然后计算n和1的与(&)运算结果,再将两数做或(|)运算,如果n和1的与(&)运算结果为1,那么结果值就加1,为0就加0。
或(|)运算的规则是当两边操作数的位有一边为1时,结果为1,否则为0。
public int reverseBits2(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n >>= 1;
}
return result;
}
04 第三种解法
先将原数转为二进制字符串,再利用StringBuilder的reverse方法得到反转的二进制字符串,再将二进制字符串变为整数返回。
public int reverseBits3(int n) {
String inputBinary = this.decimalToBinary(n);
String reversedInputBinary = new StringBuilder(inputBinary).reverse().toString();
return this.binaryToDecimal(reversedInputBinary);
}
private String decimalToBinary(int n) {
StringBuilder sb = new StringBuilder();
while (Integer.compareUnsigned(n, 0) > 0) {
sb.append(Integer.remainderUnsigned(n, 2));
n = Integer.divideUnsigned(n, 2);
}
while (sb.length() < 32) {
sb.append('0');
}
return sb.reverse().toString();
}
private int binaryToDecimal(String str) {
int res = 0;
for (char c: str.toCharArray()) {
res *= 2;
res += c == '0' ? 0 : 1;
}
return res;
}
05 第四种解法
利用包装类Integer自带的方法,reverse()方法即可反转原数。
public int reverseBits4(int n) {
return Integer.reverse(n);
}
06 小结
算法专题目前已连续日更超过一个月,算法题文章44+篇,