二进制有三种不同的表示形式:原码、反码和补码,计算机内部使用补码来表示。
•原码:就是其二进制表示(注意,有一位是符号位)
00 00 00 11 -> 3
10 00 00 11 -> -3
•反码:正数的反码就是原码,负数的反码是符号位不变,其余位取反(对应正数按位取反)
00 00 00 11 -> 3的反码
11 11 11 00 -> -3的反码
•补码:正数的补码就是原码,负数的补码是反码+1
00 00 00 11 -> 3的补码
11 11 11 01 -> -3的补码
符号位:最高位为符号位,0表示正数,1表示负数。在位运算中符号位也参与运算。
总结
•正数的原码就是其二进制,反码也是原码,补码也是原码•负数的源码就是其二进制,只不过首位是1,符号位;反码是符号位不变,其它取反;补码是反码+1;•在计算机中,负数以正值的类补码操作形式表达(取反+1)
~
~1 = 0
~0 = 1
~
把num
的补码中的0和1全部取反(0变为1, 1变为0),有符号整数的符号位在~
运算中同样会取反。
00 00 01 01 -> 5
对其取反 ~5 = -6
11 11 10 10 -> -6
11 11 10 11 -> -5
对其取反 ~(-5) = 4
00 00 01 00 -> 4
&
对位进行与操作,1与1为1,其余为0
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
只有两个对应位都为1时才为1
00 00 01 01 -> 5
&
00 00 01 10 -> 6
---
00 00 01 00 -> 4
可以看到5&6=4
|
对位进行或操作,只要有一个为1,则结果为1
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0
只要两个对应位有一个为1时就为1
00 00 01 01 -> 5
&
00 00 01 10 -> 6
---
00 00 01 11 -> 7
可以看到5|6=7
^
对位进行异或操作,只有两个元素不一样的时候为1,其余为0
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
只有两个对应位不同时才为1
00 00 01 01 -> 5
&
00 00 01 10 -> 6
---
00 00 00 11 -> 3
可以看到5^6=3
异或操作的性质:满足交换律和结合律
A: 00 00 11 00 -> 12
B: 00 00 01 11 -> 7
A^B: 00 00 10 11 -> 11
B^A: 00 00 10 11 -> 11
可以看到: A^B = B^A
另外有A^0=A
, A^A=0
A: 00 00 11 00 -> 12
A: 00 00 11 00 -> 12
0: 00 00 00 00 -> 0
A^A: 00 00 00 00 -> 0
A^0: 00 00 11 00 -> 12
另外有A^B^A = A^A^B=B
A: 00 00 11 00 -> 12
B: 00 00 01 11 -> 7
A^B: 00 00 10 11 -> 11
A: 00 00 11 00 -> 12
A^B^A: 00 00 01 11 -> 7 == B
A: 00 00 11 00
A: 00 00 11 00
A^A: 00 00 00 00
B: 00 00 01 11
A^A^B: 00 00 01 11 -> 7 == B
<<
num << i
将num
的二进制表示向左移动i
位所得的值。
00 00 10 11 -> 11
11 << 3
---
01 01 10 00 -> 88
左移一位相当于所有位置向左移动一位,末尾补零。相当于每一位都乘以2,总数也是乘以2。
这种左移操作比乘法操作要快,可以在编程的时候适当运用该位运算。
>>
num >> i
将num
的二进制表示向右移动i
位所得的值。
00 00 10 11 -> 11
11 >> 2
---
00 00 00 10 -> 2
11/2 = 5
5/2 = 2
注意python中除法应该用//
,/
的结果是浮点型
右移一位相当于所有位置向右移动一位,首位补零。相当于每一位都除以2,总数也是除以2。
这种右移操作比除法操作要快,可以在编程的时候适当运用该位运算。
•https://tianchi.aliyun.com/course/932/14644
位运算一般用于找唯一元素,常用的运算是异或,与等。具体问题可以慢慢找规律得到。
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?
示例 :
输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4
解题思路
思路一:使用哈希表的形式,元素作为key,次数作为value,但使用了额外空间
思路二:使用位运算的性质:X^X=0
X^0=X
,如果一个列表中就只存在唯一的元素,其它元素都出现两次,那么将这些运算都进行异或操作,最后剩余的元素就是唯一元素。因为两个相同的元素异或结果为0,0与唯一元素异或就是唯一元素。
•python实现
class Solution:
def singleNumber(self, nums: List[int]) -> int:
length = len(nums)
if length == 1:
return nums[0]
ans = nums[0]
for i in range(1, length):
ans ^= nums[i]
return ans
•c++实现
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(auto e: nums)
{
res ^= e;
}
return res;
}
};
给定一个整数数组 nums
,其中恰好有两个元素只出现一次,其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶:你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?
*
示例 *
输入:nums = [1,2,1,3,2,5]
输出:[3,5]
解释:[5, 3] 也是有效的答案。
输入:nums = [-1,0]
输出:[-1,0]
输入:nums = [0,1]
输出:[1,0]
解题思路:
这题与上一题有些变化,如果按照上一题的思路来看,最后异或得到的元素是只出现一次的两个元素异或的值。
比如以[1,2,1,3,2,5]
,每个元素都进行异或操作,得到的结构是3^5
00 00 00 11 -> 3
00 00 01 01 -> 5
3^5
---
00 00 01 10 -> 6
再看一下6的负数-6的二进制,
00 00 01 10
11 11 10 10 -> -6
6与-6进行与操作
6&-6
---
00 00 00 10 -> 2可以看到,只保留一位上有1
再观察1,2,3,5的二进制形式:
00 00 00 01 -> 1
00 00 00 10 -> 2
00 00 00 11 -> 3
00 00 01 01 -> 5
1与2进行与操作
00 00 00 00
2与2进行与操作
00 00 00 10
3与2进行与操作
00 00 00 10
5与2进行与操作
00 00 00 00
可以看到1与5的结果是一样的,2与3的结果是一样的。
这些元素与6&-6得到的结果进行与操作,就能保留出那一个位置上有1的,基于此将列表分为两部分,每部分都只有一个唯一元素存在`[1, 1, 5]`与`[2, 2, 3]`,题目又转化为上一题的样式,最终将结果进行合并即可。
•python实现
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
length = len(nums)
if length == 2:
return nums
inner_num = 0
for num in nums:
inner_num ^= num
inner_num &= (-inner_num)
num1 = 0
num2 = 0
for num in nums:
if num & inner_num:
num1 ^= num
else:
num2 ^= num
return [num1, num2]
•c++实现
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int length = nums.size();
if(length==2)
{
return nums;
}
int inner_num = 0;
for(auto num: nums)
{
inner_num ^= num;
}
int lsb = (inner_num == INT_MIN ? inner_num: inner_num & (-inner_num)); // 防止溢出
int num1 = 0;
int num2 = 0;
for(auto num: nums)
{
if(num & lsb)
{
num1 ^= num;
}
else
{
num2 ^= num;
}
}
return {num1, num2};
}
};
给你一个整数数组 nums
,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 :
输入:nums = [2,2,3,2]
输出:3
输入:nums = [0,1,0,1,0,1,99]
输出:99
解题思路:
•哈希表的方式,统计元素出现次数,再进行遍历一次找出出现一次的元素•位运算:考虑二进制的每一位,如果是三个数的,则相加为3或者0,多的那个数加起来的那位,整除3的余数就是出现一次的元素。由于数组中的元素都在 int
(即32位整数)范围内,因此可以依次计算答案的每一个二进制位是1还是0 。具体地,考虑答案的第i
个二进制位( i
从0
开始编号),它可能为1 或 0。对于数组中出现三次的元素,每一个元素都出现了3次,对应着第i
个二进制位的 3个0 或3 个1 ,无论是哪一种情况,它们的和都是3的倍数(即和为3或0 )。因此:
答案的第 个二进制位就是数组中所有元素的第
i
个二进制位之和除以3的余数。
这样一来,对于数组中的每一个元素 ,我们使用位运算 得到 的第 个二进制位,并将它们相加再对 取余,得到的结果一定为 或 ,即为答案的第 个二进制位。
细节
需要注意的是,如果使用的语言对「有符号整数类型」和「无符号整数类型」没有区分,那么可能会得到错误的答案。这是因为「有符号整数类型」(即 类型)的第31个二进制位(即最高位)是补码意义下的符号位,对应着 符号位,而「无符号整数类型」由于没有符号,第31个二进制位对应着2^{31} 。因此在某些语言(例如python )中需要对最高位进行特殊判断。
python实现代码
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for i in range(32):
total = sum((num>>i) &1 for num in nums) # 右移的元素与1与,得到最末尾元素是0/1
if total % 3:
if i == 31:
ans -= (1<<i) # 31位置为1,表明是符号位
else:
ans |= (1<<i) # 或等表明获得该位置的值
return ans
c++实现代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for(int i=0; i<32; i++)
{
int total = 0;
for(int num: nums)
{
total += ((num >> i) & 1);
}
if(total % 3)
{
ans |= (1<<i);
}
}
return ans;
}
};
给你一个整数 n
,请你判断该整数是否是 2 的幂次方。如果是,返回 true
;否则,返回 false
。
如果存在一个整数 x 使得n == 2^x ,则认为 n 是 2 的幂次方。
示例 :
输入:n = 1
输出:true
解释:20 = 1
输入:n = 16
输出:true
解释:24 = 16
输入:n = 3
输出:false
输入:n = 4
输出:true
输入:n = 5
输出:false
解题思路
方法1:使用while循环一直除以2,看能不能结果为是否为0(1排外)
方法2:一个数n
是2的幂,当且仅当n
是正整数,并且n
的二进制表示中仅包含1个1。
使用位运算,自身与真身-1后进行与运算。如果是2的幂的话,则表明二进制位有值的是1,减1之后的二进制位最低位的1变成0,其后跟的0变成1,再与本身进行与,则将最低位的1消掉;n&(n-1)
,判断最终的结构是否为0
除了1之外,其它2的幂指数的二进制表示就只有1个1。幂指数不可能为负
如果n
是正整数并且n&(n-1)==0
,那么n
就是2的幂。
另外考虑如果n
是正整数并且n&(-n)==n
, 那么n
也是2的幂
•python实现
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n == 1:
return True
return n > 0 and (n & (n-1)) == 0 # 幂指数不可能为负
•c++实现
class Solution {
public:
bool isPowerOfTwo(int n) {
if (n==1)
{
return true;
}
return n > 0 && (n& (n-1)) == 0;
}
};
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 :
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
输入:nums = [0]
输出:[[],[0]]
解题思路:
观察结果可以看到,列表中肯定有一个空子集,其它的都是罗列出来的元素,从0个,1个,一直到最终整个列表。可以通过递归的方法获得结果。
•python实现
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
if nums is None or len(nums) < 1:
return [[]]
length = len(nums)
res = []
def helper(i, tmp):
res.append(tmp)
for j in range(i, length): # 循环结束时候就是回溯开始之时
helper(j+1, tmp+[nums[j]])
helper(0, [])
return res
•c++实现
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
void dfs(int cur, vector<int>& nums) {
if (cur == nums.size()) {
ans.push_back(t);
return;
}
// 考虑选择当前位置
t.push_back(nums[cur]);
dfs(cur + 1, nums);
t.pop_back();
// 考虑不选择当前位置
dfs(cur + 1, nums);
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(0, nums);
return ans;
}
};