目录
二进制算法
二进制转十进制
例如：1010 从左边开始：
1*2^3+0*2^2+1*2^1+0*2^0=10
例如：1011 从左边开始：
1*2^3+0*2^2+1*2^1+1*2^0=11
例如：1111 从左边开始：
1*2^3+1*2^2+1*2^1+1*2^0=15
十进制转二进制
将余数从下向上倒序写
例如：10 故二进制为：1010
10/2=5余0
5/2=2余1
2/2=1余0
1/2=0余1
例如：15 故二进制为：1111
15/2=7余1
7/2=3余1
3/2=1余1
1/2=0余1
例如：16 故二进制为：10000
16/2=8余0
8/2=4余0
4/2=2余0
2/2=1余0
1/2=0余1
位运算概念
位运算分为两大类：逻辑运算符，位移运算符
逻辑运算符：
位与：C语言中&表示,相同位都为1才为1，否则为0
位或：C语言中｜表示,相同位都为0才为0，否则为1
异或：C语言中^表示,两个位相同时为0，不同时为1
按位取反：C语言中~表示
位移运算符：
左移：C语言中<<表示
右移：C语言中>>表示
位与&
符号：&
位与：相同位都为1才为1，否则为0
10-->1010
& 11-->1011
------------
1010-->10
位与：
14-->1110
& 11-->1011
------------
1010-->10
位或｜
符号：|
位或：相同位都为0才为0，否则为1
10-->1010
| 11-->1011
------------
1011-->11
位或：
14-->1110
11-->1011
----------
1111-->15
异或^
符号：^
异或：相同位都相同为0，否则为1
10-->1010
^ 11-->1011
------------
0001-->1
异或：
14-->1110
11-->1011
----------
0101-->5
/*
异或公式：
1:a^a=0,相同的数"^"异或为0
2:a^0=a,任何数与0“^”异或为本身
3:a^b=b^a,满足交换律
4:(a^b)^c=a^(b^c),满足结合律
*/
按位取反~
符号：~ 一元运算
按位取反：0变1，1变0，高位不足0补全
10-->1010
----------
0101-->5
11-->1011
----------
0100-->4
左移<<
符号：<<
左移：x<<y,表示x向左移动了y位，末尾补0
左移：10<<1
10-->1010
----------
10100-->2^4+2^2=16+4=20
左移：10<<2
10-->1010
----------
101000-->2^5+2^3=32+8=40
左移：10<<3
10-->1010
----------
1010000-->2^6+2^4=64+16=80
分析：左移1位相当于对x乘2，左移2位相当于对x乘(2*2),左移3位相当于对x乘(2*2*2)
总结：x<<y = x*(2^y)
右移>>
符号：>>
右移：x>>y,表示x向右移动了y位，如果x是非负数，则高位补0。如果x是负数则高位补1
右移：11>>1
11-->1011
----------
0101-->5
右移：11>>2
11-->1011
----------
0010-->2
右移：11>>3
11-->1011
----------
0001-->1
右移：11>>4
11-->1011
----------
0000-->0
分析：右移1位相当于对x除2并取整，左移2位相当于对x除(2*2),左移3位相当于对x除(2*2*2)
总结：x>>y = x/(2^y)
位算法实践
2的幂
题目：给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
答案：
/*
通过位与实现
思路分析：如果n是2的幂，二进制必然为:100000若干0，n-1二进制为:011111若干1。n&(n-1)=0
100000
& 011111
--------
000000
*/
func isPower(n int) bool {
return (n&(n-1)) == 0 && n > 0
}
4的幂
题目：给你一个整数 n，请你判断该整数是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
答案：
/*
通过位与实现
思路分析：
2^2x mod3 = 1 --> 4^x mod3 = 1
2^(2x+1)mod3 = 2
综上：三个条件可以判断是否为4的幂
1:n>2
2:n为2的幂
3.n mod3=1
*/
func isPower(n int) bool {
return n > 0 && (n&(n-1)) == 0 && n%3==1
}
二进制"1"的个数
题目：输出二进制为“1”的个数
解析：每一次n&(n-1)都会消除一个“1”，记录消除“1”的次数就是“1”的个数
/*
77
76/2=38..1
38/2=19..0
19/2=9..1
9/2=4..1
4/2=2..0
2/2=1..0
1/2=0..1
二进制为: 1001101
1001101 -->77
& 1001100 -->76
----------
1001100 -->76
& 1001011 -->75
----------
1001000 -->72
& 1000111 -->71
---------------
1000000 -->64
& 0111111 -->63
----------------
0000000 -->0
*/
func hamming(n int) int {
k := 0
for n != 0 {
n &= (n - 1)
fmt.Println(n)
k++
}
return k
}
交换数字
题目：编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。
示例：
输入: numbers = [1,2]
输出: [2,1]
答案1：
/*
交叉赋值，其他语言可能不支持，所以看第二种：位运算方式
*/
func swapNumbers(numbers []int) []int {
numbers[0], numbers[1] = numbers[1], numbers[0]
return numbers
}
答案2:
/*
异或：两个位相同时为0，不同时为1
前序算法：
1.相同的数"^"异或为0
2.任何数与0“^”异或为本身
比较难理解:
a=a^b
b=a^b=a^b^b=a^0=a
a=a^b=a^b^a=a^a^b=b
*/
func swapNumbers2(numbers []int) []int {
numbers[0] = numbers[0] ^ numbers[1]
numbers[1] = numbers[0] ^ numbers[1]
numbers[0] = numbers[0] ^ numbers[1]
return numbers
}
只出现一次的数字
题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
答案：
/*
异或公式：
1:a^a=0,相同的数"^"异或为0
2:a^0=a,任何数与0“^”异或为本身
3:a^b=b^a,满足交换律
4:(a^b)^c=a^(b^c),满足结合律
题目解析：
把数组中所有的数异，相同的数异或完必然为0，所有数和0异或等于本身，所以数组中全部异或完必然只出现1次的数
*/
func singleNumber(nums []int) int {
t := 0
for _, v := range nums {
t = t ^ v
}
return t
}
func main() {
number := []int{1, 1, 2, 5, 5}
fmt.Println(singleNumber(number))
}
汉明距离
题目：两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：
输入：x = 3, y = 1
输出：1
解释：
3 (0 0 1 1)
1 (0 0 0 1)
↑ ↑
交替位二进制数
题目：给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
示例 1：
输入：n = 5
输出：true
解释：5 的二进制表示是：101
示例 2：
输入：n = 7
输出：false
解释：7 的二进制表示是：111
示例 3：
输入：n = 11
输出：false
解释：11 的二进制表示是：1011
答案：
/*
位与：相同位都为1才为1，否则为0
解析：
第一步：3的二进制为"11"，n位与3，两种情况相邻数字相同：00和11,所以n&3==0 或者 n&3==3 为False
第二步：n左移一位，进行下一轮比较。直到左移完毕，为0
5-->1101
& 3--> 11
------------
01 -->1 第一轮：true
5--> 110 第二轮：左移一位
& 3--> 11
------------
10 -->2 第二轮：true
5--> 11 第三轮：再左移一位
& 3--> 11
------------
11 -->3 第三轮：False
*/
func hasAlternatingBits(n int) bool {
for n != 0 {
if n&3 == 3 || n&3 == 0 {
return false
}
n >>= 1
}
return true
}
func main() {
fmt.Println(hasAlternatingBits(5))
}
两整数只和(不使用+-)
题目：两整数之和(不使用+-)
示例 1：
输入：a = 1, b = 2
输出：3
答案：
/*
解析：sum = (a ^ b) +((a & b) << 1),但是不能有"+"号，所以递归处理，出口为b==0
10+10:
10^10:
1010
^ 1010
-----
0000
(10^10)<<1
1010
& 1010
-----
1010
<<1
-----
10100
10100+0000=10100-->20
11+9:
11^9:
1011
^ 1001
-----
0010
(11&9)<<1:
1011
& 1001
-----
1001
<<1
------
10010
10010+0010=10100-->20
*/
func getSum(a int, b int) int {
if b == 0 {
return a
}
return getSum(a^b, a&b<<1)
}
func main() {
fmt.Println(getSum2(1, 2))
}