【算法】位运算| & ^ ~ -n n-1

目录

1.| 

2.&

3.^

3.1相加和位

3.1.1无进位去和

3.1.2进位去和

4.~

5.-n

6.n-1

位图

1.| 

1占侧：|1 占1 ，|0 化原，同 | 同 为同

2.&

0占侧：&0 占0 ，&1 化原，同 & 同 为同

3.^

无进位加法：^0 和原，同 ^ 同 消0

3.1相加和位

化二进制bit位01 去进位/无进位相加和的位上查

3.1.1无进位去和

260. 只出现一次的数字 III - 力扣（LeetCode）

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

输入：nums = [1,2,1,3,2,5] 输出：[3,5] 解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0] 输出：[-1,0]

示例 3：

输入：nums = [0,1] 输出：[1,0]

提示：

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

public int[] singleNumber(int[] nums) { int sum = 0; for (int i : nums) sum ^= i; // sum:两个不同数的^和 int tmp1 = sum & -sum; // a和b不同，肯定有一位比特位为1，tmp1:右首1提纯数 // 各只出现1次的 不同的 两个数 和1位 肯定不同，一个是0 一个是1，各分开在 此位为01的 2组中，其余出现2次的 都各成对分布在两组中 和为0，分开来两组消和 两不同数各出 int[] ret = new int[2]; for (int i : nums) { //if((i & tmp1) == 0) if((i & tmp1) != 0) // 右首1这位 为1的 这组，两个不同数的其中一个 这位是1的 分到这组 ret[0] ^= i; else ret[1] ^= i; // 右首1这位 为0的 这组，两个不同数的其中一个 这位是0的 分到这组 } return ret; }

3.1.2进位去和

137. 只出现一次的数字 || - 力扣（LeetCode）

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2] 输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99] 输出：99

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

public int singleNumber(int[] nums) { int ret = 0; for (int i = 0; i < 32; i++) { int sum = 0; for (int x : nums) if (((x >> i & 1) == 1)) sum++; if(sum % 3 == 1) ret |= 1 << i; }return ret; }

4.~

取反

5.-n

右首1 往左取反， n & -n 右首1纯提

6.n-1

右首1 含右取反，n & (n-1) 右首1化0

位图

用数变量的二进制槽子存bit01 代 对值

面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = "leetcode" 输出: false

示例 2：

输入: s = "abc" 输出: true

限制：

• 0 <= len(s) <= 100
• s[i]仅包含小写字母
• 如果你不使用额外的数据结构，会很加分。

public boolean isUnique(String astr) { // 鸽巢原理优化： if(astr.length() > 26) return false; int bitMap = 0; // 位图数变量 for (int i = 0; i < astr.length(); i++) { int x = astr.charAt(i) - 'a'; // 判断字符是否已存在位图中： if(((bitMap >> x) & 1) == 1) return false; // 把此字符在位图中标记存在： bitMap |= (1 << x); } return true; }