力扣位运算基础知识,今天小编就来聊一聊关于掌握java运算符的心得?接下来我们就一起去研究一下吧!
![掌握java运算符的心得(Java中关于位运算的一些小技巧)](http://img.studyofnet.com/upimg/951047438.jpg)
掌握java运算符的心得
力扣
知识预备位运算基础知识
原题给你一个非负整数 num ,请你返回将它变成 0 所需要的步数。 如果当前数字是偶数,你需要把它除以 2 ;否则,减去 1 。
示例 1:
输入: num = 14 输出: 6
解释:
示例 2:
输入: num = 8 输出: 4
解释:
示例 3:
输入: num = 123 输出: 12
提示:
经过研究,其中其实隐藏了规则
- 如果这个数字是2的n次方,那么他的题目步数其实就是log2(log2为底),也就是求这个n是多少。
- 如果不是2的n次方,那么其实就只能按照常规方案计算,奇数减一,偶数除2。
- 为了运算正常,其中会有大量的取模运算,为了判断是技术还是偶数
那么这里我考虑到这里就非常适合使用位运算来计算,可以解决2个需要运算耗时的地方
- Q: 判断数字是不是2的n次方,只有等于了才能去计算这个n是多少
A:使用 (num & (num - 1)) == 0 来判断是否是2的n次方
因为如果数字是2的n次方,那么他的二进制必然是类似 00010000,只会存在一个1,然后num-1 就会变成 00001111,两边通过&运算,一定是没有相同的1,所以结果一定为0,就可以判断是否是2的n次方。
假设 num = 16:
16&16-1 = 00010000 & 00001111 = 0 ✅
假设 num = 15:
15&15-1 = 00001111 & 00001110 = 14 ❌
A: 使用(num & 1) == 0 判断是奇数还是偶数,相当于替换 num % 2 == 0 。这里的原因其实是判断奇数还是偶数的核心就是数字二进制的最后一位是什么,如果是奇数,一定是1。
那么判断奇数偶数的问题就转变成了判断二进制最后一位是0还是1的问题。
这样通过二进制的 & 操作就可帮助我们快速判断是基数还是偶数。
假设 num = 16:
16&1 = 00010000 & 00000001 = 0 ✅
假设 num = 15:
15&1 = 00001111 & 00000001 = 1 ❌
实践样例代码
public int numberOfSteps(int num) {
int count = 0;
while (num != 0) {
if ((num & (num - 1)) == 0) {
double v = Math.log(num) / Math.log(2);
return (int) v 1 count;
}
//偶数
if ((num & 1) == 0) {
num = num / 2;
count ;
}
//奇数
if ((num & 1) != 0) {
num = num - 1;
count ;
}
}
return count;
}
执行效率和内存还是很不错的,执行时间约等于1ms,内存使用率低于百分之97的java提交,对比与官方题解,我这种方案认为也还可以。
结尾按照上述的方案就是针对位运算的一点小技巧,因为其实在常规的开发中,我们其实是不太会用位运算,原因我大概理解为以下几个
- 阅读位运算代码成本较高
- 业务上还不至于在这种细节点扣
- 位运算代码书写不够熟练
但个人理解,如果能一点一点开始位运算的话,可以在需要的时候尽可能的增加计算效率并且做leetCode的时候比较有用。
作者介绍欢迎点赞,关注博主,未来会有更多知识解答,有问题可以评论区讨论,尽全力帮大家解答。