- 基础：
- << : 左移运算符，num << 1,相当于num乘以2
- >> : 右移运算符，num >> 1,相当于num除以2
- >>> : 无符号右移，忽略符号位，空位都以0补齐
- 原码，反码，补码。正数的原码，反码，补码都一样，负数的反码是对除了符号位（最高位）对原码取反，补码是对反码+1
- 负数的带符号移位时，最高位——符号位，不变
- 判断2的次方数
如果一个数是2的次方数的话，根据上面分析，那么它的二进数必然是最高位为1，其它都为0，那么如果此时我们减1的话，则最高位会降一位，其余为0的位现在都为变为1，那么我们把两数相与，就会得到0，用这个性质也能来解题，而且只需一行代码就可以搞定，如下所示
class Solution {
public:
public boolean isPowerOfTwo(int n) {
if(n > 0)
{
if((n & (n - 1)) == 0)
return true;
}
return false;
}
};
- 判断3的次方数
高中学过的换底公式为logab = logcb / logca，那么如果n是3的倍数，则log3n一定是整数，我们利用换底公式可以写为log3n = log10n / log103，注意这里一定要用10为底数，不能用自然数或者2为底数，否则当n=243时会出错，原因请看这个帖子。现在问题就变成了判断log10n / log103是否为整数，在c++中判断数字a是否为整数，我们可以用 a - int(a) == 0 来判断
class Solution {
public:
public boolean isPowerOfFour(int num) {
return (num>0 && (isIntegerForDouble(Math.log(num)/ Math.log(3))) );
}
public static boolean isIntegerForDouble(double obj) {
double eps = 1e-10; // 精度范围
return obj-Math.floor(obj) < eps;
}
};
- 判断4的次方数
同上，log的换底公式 - 按位翻转
思路：每次取最右位的数字，然后判断是1还是0
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int result = 0;
for(int i=0;i<32;i++){
if((n&1) == 1){
result = (result <<1) +1;
}else{
result = (result <<1);
}
n=n>>1;
}
return result;
}
}
- 找到数组里落单的一个数字——数组里除了一个数字出现1次之外，其他都出现了2次
采用异或的方法。
class Solution {
public int singleNumber(int[] nums) {
if(nums == null || nums.length == 0)
return -1;
int result = 0;
for(int cur: nums){
result ^= cur;
}
return result;
}
}
- 找到s和t字符串之间，唯一不同的那个元素char——思路同6
class Solution {
public char findTheDifference(String s, String t) {
char[] a = s.toCharArray();
char[] b = t.toCharArray();
int result = 0;
for(char cur: a){
result ^= cur;
}
for(char cur: b){
result ^= cur;
}
return (char) result;
}
}
- 给出3*n + 1 个非负整数，除其中一个数字之外其他每个数字均出现三次，找到这个数字
思路： 利用位操作 Bit Operation 来解此题。建立一个32位的数字，来统计输入数组各元素之和。
需要每次对各元素同一bit位进行加和，如果这个数字出现过3次，那么%3=0；如果只出现过1次，%3！=0，而且余多少，改数字的这bit位上就是多少。
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for(int i =0;i<32; i++){
int sum = 0;
for(int cur: nums){
sum += (cur >> i) & 1;
}
result |= (sum % 3) << i;
}
return result;
}
}
- 求子集，列出所有结果——这个不是bit operation，是数组的移位
class Solution {
public List<List<Integer>> subsets(int[] nums) {
if(nums == null || nums.length ==0)
return [];
List<List<Integer>> res = new ArrayList<List<Integer>>();
res.add(new ArrayList<Integer>());
for(int cur: nums){
int size = res.size();
for(int i=0; i<size; i ++){
List<Integer> cur_list = new ArrayList<>(res.get(i));
cur_list.add(cur);
res.add(cur_list);
}
}
return res;
}
}
- 求重复的DNA序列
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"]
思路：A: 0100 0001 C: 0100 0011 G: 0100 0111 T: 0101 0100
由于我们的目的是利用位来区分字符，当然是越少位越好，通过观察发现，每个字符的后三位都不相同，故而我们可以用末尾三位来区分这四个字符。而题目要求是10个字符长度的串，每个字符用三位来区分，10个字符需要30位，在32位机上也OK。为了提取出后30位，我们还需要用个mask，取值为0x7ffffff，用此mask可取出后27位，再向左平移三位即可。算法的思想是，当取出第十个字符时，将其存在哈希表里，和该字符串出现频率映射，之后每向左移三位替换一个字符，查找新字符串在哈希表里出现次数，如果之前刚好出现过一次，则将当前字符串存入返回值的数组并将其出现次数加一，如果从未出现过，则将其映射到1。为了能更清楚的阐述整个过程，我们用题目中给的例子来分析整个过程：
首先我们取出前九个字符AAAAACCCC，根据上面的分析，我们用三位来表示一个字符，所以这九个字符可以用二进制表示为001001001001011011011，然后我们继续遍历字符串，下一个进来的是C，则当前字符为AAAAACCCCC，二进制表示为001001001001011011011011，然后我们将其存入哈希表中，用二进制的好处是可以用一个int变量来表示任意十个字符序列，比起直接存入字符串大大的节省了内存空间，然后再读入下一个字符C，则此时字符串为AAAACCCCCA，我们还是存入其二进制的表示形式，以此类推，当某个序列之前已经出现过了，我们将其存入结果res中即可
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> res = new ArrayList<String>();
if(s==null || s.length() < 10)
return res;
char[] chars = s.toCharArray();
Set<Integer> combinesIntegers = new HashSet<Integer>();
int mask = 0x7ffffff; // 掩码：能够提取低27位（也就是后面9个字符）
int i =0; // 数组遍历的角标
int cur = 0; // 当前窗口为10的字符串，用一个数字表示的结果
while(i<9){
cur = (cur << 3) | (chars[i++] & 7); // ACGT，每个字母用3个数字表示。所以用7(0b111即可作为当前字母的提取掩码)
// i++;
}
while(i < s.length()){
cur = ((cur & mask) << 3) | (chars[i++] & 7);
if(combinesIntegers.contains(cur)){ // 如果哈希表里已有，说明之前这个四个字母的组合已经出现过，即可加入返回队列里
String target = s.substring(i-10,i);
if(res.contains(target) == false){ // 判断，返回队列不要有重复数据
res.add(target);
}
}else{
combinesIntegers.add(cur);
}
// i++;
}
return res;
}
}
- 数字范围相与
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
只要写代码找到m和n的左边公共的部分即可
class Solution {
public int rangeBitwiseAnd(int m, int n) {
if(m == n)
return m;
int mask = 0xffffffff;
while((m & mask) != (n & mask)){
mask = mask << 1;
}
return m & mask;
}
}
- 给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。
分析：
- 异或：两个相同数字异或，结果为0；0与任意数异或，结果是其本身
- a & (-a)： 可以得到这个数字里某一位为1的值。 is a trick to extract the lowest set bit of i
- a & 1: 获取数字最低位
- 解题：（1） 从前往后遍历，所有数字异或的结果=那两个特别数字异或的结果xor
（2） 将nums分为两大阵营：将xor转化为只保留某一位为1、其他为0的数字， 然后与各个nums数字与操作。=1 PK =0，自然分为两大阵营。
class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0; // 用于保存异或结果
int group0=0; // 用于保存第一组的异或结果
int group1=0; // 用户保存第二组的异或结果
for(int cur: nums){
xor ^= cur;
}
xor = xor &(-xor); // 这个公式，可以求出xor里某一位=1的数字
for(int cur: nums){
if( (xor & cur) == 0){
group0 ^= cur;
}
else{
group1 ^= cur;
}
}
int[] returns = new int[2];
returns[0] = group0;
returns[1] = group1;
return returns;
}
}
- 单词长度的最大积——让我们求两个没有相同字母的单词的长度之积的最大值
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
示例 1:
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
示例 2:
输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。
因为题目中说都是小写字母，那么只有26位，一个整型数int有32位，我们可以用后26位来对应26个字母，若为1，说明该对应位置的字母出现过；进而我们也可以用一个int数字表示一个英文单词。
这样判断两个单词没有共同字母的条件是：这两个int数 相与结果=0
class Solution {
public int maxProduct(String[] words) {
if(words == null || words.length <= 1 ){
return 0;
}
int max_product = 0;
List<Integer> mask = new ArrayList<Integer>(); // 因为都是小写字母，总数最多26个。所以可以用一个32位的Int，用其二进制表示法 表示一个字母，而且bit中为1的只有一个。因此一个单词，也同样可以用一个二进制数表示。
for(int i =0 ; i< words.length;i++){
// 计算 当前单词的mask值
int cur_mask = 0;
for(char cur: words[i].toCharArray()){
cur_mask |= (1 << (cur-'a'));
}
mask.add(cur_mask);
// 遍历i之前的那些数组
for(int j =0; j <i; j++){
if((mask.get(i) & mask.get(j)) == 0){
max_product = Math.max(max_product, words[i].length() * words[j].length());
}
}
}
return max_product;
}
}
- Sum of Two Integers——不用+、-， 但要求计算出两个数字之和
- 两个数字 如果忽略进位 求和可用异或计算
- 两个数字的进位 可用与计算
class Solution {
public int getSum(int a, int b) {
int xor = a ^ b;
int carray = (a & b) <<1 ;
if(carray != 0 ){
return getSum(xor, carray);
}
return xor;
}
}
- 将数字转换为16进制——给定一个整数，写一个函数将其转换为16进制，不能用系统自带的进制转换函数
mask固定
class Solution {
public String toHex(int num) {
if(num == 0) {
return "0";
}
String ans = "";
int len = 0;
while(num != 0 && len < 8) {
int bit = num & 15;
if(bit < 10) {
ans = (char)('0' + bit) + ans;
}
else {
ans = (char)('a' + bit - 10) + ans;
}
num >>= 4;
len++;
}
return ans;
}
}
- 整数替换
If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n - 1.
思路：
利用bit位的操作。如果这个数偶数，那么末位的bit位一定是0。如果一个数是奇数，那么末位的bit位一定是1。对于偶数，操作是直接除以2。
对于奇数的操作:
如果倒数第二位是0，那么n-1的操作比n+1的操作能消掉更多的1。
1001 + 1 = 1010
1001 - 1 = 1000
如果倒数第二位是1，那么n+1的操作能比n-1的操作消掉更多的1。
1011 + 1 = 1100
1111 + 1 = 10000
public int integerReplacement(int n) {
// 处理大数据的时候tricky part, 用Long来代替int数据
long N = n;
int count = 0;
while(N != 1) {
if(N % 2 == 0) {
N = N >> 1;
}
else {
// corner case;
if(N == 3) {
count += 2;
break;
}
N = (N & 2) == 2 ? N + 1 : N - 1;
}
count ++;
}
return count;
}
- x&(-x):
如果x是奇数，则返回1
如果x是偶数，则返回 最右bit=1的数字，该数也是：能整除这个偶数的最大的2的幂(即： y = x & -x , 则 x % y = 0, 且 y = 2 ^ k). 例如x=12时，12&(-12)=0100=4
i & (~i + 1) is a trick to extract the lowest set bit of i.
