java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 |
---|
分组位运算
这道题正常来说可以用转换7进制的思想来,但是题目有特殊要求,负数要求补码形式,就不能用这个思路,只能用位运算了,有兴趣的可以参考
🏆LeetCode504. 七进制数https://blog.csdn.net/grd_java/article/details/137261543 |
---|
解题思路:时间复杂度O(
k
k
k),空间复杂度O(
k
k
k),k是16进制的二进制组数(4位一组),32位共8组,k=8 |
---|
- 26的二进制(补码)为:
0000,0000,0000,0000,0000,0000,0001,1010
,对应的组号为7组,6组,5组,4组,3组,2组,1组,0组
- 我们都知道8421码是二进制转换为16进制常用的方法,例如
二进制1010的8421码为1*8+0*4+1*2+0*1 = 8+0+2+1 = 10 = a
- 也就是说,只要我们每次只截取4位单独进行8421转换,就可以完成16进制的转换
- 但是如何用计算机实现这个效果呢?我们如何将其按4位为一组截取出来呢?
- 16进制最大的值是15也就是0xf。对应二进制为
0000,0000,0000,0000,0000,0000,0000,1111
。 - 我们只需要将
任意值
与(&) 0xf
就可以只得到最后4位,其余全是0. - 例如26的二进制(补码)为:
0000,0000,0000,0000,0000,0000,0001,1010
,与上&
,15这个数0xf
,也就是
0000,0000,0000,0000,0000,0000,0000,1111
=
0000,0000,0000,0000,0000,0000,0000,1010
= 10.我们发现成功将第0组截取了出来 - 然后我们对26右移4位,变成
0000,0000,0000,0000,0000,0000,0000,0001
,与上&
,15这个数0xf
,也就是
0000,0000,0000,0000,0000,0000,0000,1111
=
0000,0000,0000,0000,0000,0000,0000,0001
= 1.我们发现成功将第1组截取了出来
也就是说,想要对应的组数,例如最后一组7组,只需要将0-6组全部右位移走,然后与上0xf即可获取,简单来说就是[7组,6组,5组,4组,3组,2组,1组,0组] 右位移(>>) 6组 = [0,0,0,0,0,0,0,7组]
,[7组,6组,5组,4组,3组,2组,1组,0组] 右位移(>>) 3组 = [0,0,0,7组,6组,5组,4组,3组]
,此时与上0fx就会截取最低位的一组
- 对应到二进制上,组只是我们对其规划的,实际上需要一个二进制一个二进制的位移。
- 例如右移6组,就需要右位移
6*4=24位二进制
.我们发现如果想要位移0组就位移0*4个二进制
,想要位移1组,就位移1*4个二进制
,想要第7组就需要右位移6组,就需要位移6*4个二进制位
- 因此,我们可以搞一个for循环,循环7次,第一次取第7组,第二次取第6组…
class Solution {
static final char[] digits = {
'0' , '1' , '2' , '3' , '4' , '5' ,
'6' , '7' , '8' , '9' , 'a' , 'b' ,
'c' , 'd' , 'e' , 'f' , 'g' , 'h' ,
'i' , 'j' , 'k' , 'l' , 'm' , 'n' ,
'o' , 'p' , 'q' , 'r' , 's' , 't' ,
'u' , 'v' , 'w' , 'x' , 'y' , 'z'
};
public String toHex(int num) {
if (num == 0) return "0";
StringBuffer sb = new StringBuffer();
for (int i = 7; i >= 0; i --) {
int val = (num >> (4 * i)) & 0xf;
if (sb.length() > 0 || val > 0) {
char digit = digits[val];
sb.append(digit);
}
}
return sb.toString();
}
}