LeetCode通关:求次数有妙招,位运算三连
2021/8/3 23:06:52
本文主要是介绍LeetCode通关:求次数有妙招,位运算三连,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
分门别类刷算法,坚持,进步!
刷题路线参考: https://github.com/chefyuan/algorithm-base
大家好,我是刷题困难户老三,这一节我们来刷几道很有意思的求次数问题
,它们都有同一类非常巧妙的解法。
这种解法是什么呢?往下看吧!
基础知识
在开始之前,我们最好先了解一些位运算的基础知识。
原反补码
先简单说一下,原码、反码、补码。
一个数在计算机中的二进制表示形式, 叫做这个数的机器数。机器数是带符号的,在计算机用一个数的最高位存放符号, 正数为0, 负数为1.
比如,十进制中的数 +3 ,假如计算机字长为8位,转换成二进制就是00000011。如果是 -3 ,就是 10000011 。
- 原码
原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:
[+1]原 = 0000 0001
[-1]原 = 1000 0001
- 反码
正数的反码是其本身
负数的反码是在其原码的基础上, 符号位不变,其余各个位取反。
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
- 补码
正数的补码就是其本身
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补
补码是人脑认识里不太直观的一种表示方式,之所以发明补码,是为了让机器以一种一致的方式来处理加法运算。
更多知识建议阅读《j计算机组成原理》。
与或非异或运算
在处理整型数值时,位运算符可以直接对组成整型数值的各个位进行操作。这些位运算符在位模式下工作。位运算符包括:&
、|
、~
、^
- 与(&)
对应位都为1,结果为1,否则结果为0
int a=129; int b=128; System.out.println("a与b的结果:"+(a&b)); # 输出 a与b的结果:128
计算过程如下:
10000001 & 10000000 = 10000000
- 或(|)
对应位只要有一个为1,结果是1,否则就为0
int a=129; int b=128; System.out.println("a或b的结果:"+(a|b)); # 输出 a或b的结果是:129
计算过程如下:
10000001 | 10000000 = 10000001
- 非(~)
位为0,结果是1;位为1,结果是0
int a = 8; System.out.println("非a的结果:"+(~a)); # 输出 非a的结果:-9
计算过程如下
//8转换为二进制 1000 // 补符号位 01000 // 取反 10111 (补码) // 转源码除符号位取反+1 11001
- 异或(^)
对应位相同,结果是0,否则结果是1
1111 ^ 0010 = 1101
移位运算
移位运算见名知意,是数字二进位的移动,我们这里只讨论int型的移位运算。
- << 左移运算符
数值的补码全部左移若干位,符号位和高位丢弃,低位补 0。
- >> 右移运算符
数值的补码全部右移若干位,符号位不变。
假如int是8位二进制,两个例子如下:
10的补码为0000 1010,左移一位变成20(0001 0100),右移一位变成5(0000 0101)
5的补码为0000 0101,左移一位变成10(0000 1010),右移一位变成2(0000 0010)
求次数问题
LeetCode136. 只出现一次的数字
☕ 题目:136. 只出现一次的数字 (https://leetcode-cn.com/problems/single-number/)
❓ 难度:简单
这篇关于LeetCode通关:求次数有妙招,位运算三连的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享