Tag Archives: bit manipulation

Leetcode: Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

解法1:求和

public class Solution {
    public int missingNumber(int[] nums) {
        int total = nums.length;
        int sum = total * (total + 1 ) / 2;
        int actual = 0;
        for (int num : nums) {
            actual += num;
        }
        return sum - actual;
    }
}

解法2: bit manipulation， 将所有出现的数与所有应该出现的数亦或

public class Solution {
    public int missingNumber(int[] nums) {
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= nums[i] ^= (i + 1);
        }
        return xor;
    }
}

Integer Replacement

Given a positive integer n and you can do operations as follow:

If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n – 1.
What is the minimum number of replacements needed for n to become 1?
关键点在于当n是基数时，如果倒数第二位是0， 那么减1， 否则加1
另外一定使用>>>而不是>>, >>>会在前面补0，当n为max时，补完零是负数，因此while条件是n!=1， 而不是n > 1.

public class Solution {
    public int integerReplacement(int n) {
        int result = 0;
        while (n != 1) {// n > 1 won't work for max value, as n >>>= 1 will be negative
            if (n == 3) {
                return result + 2;
            }
            if ((n & 1) != 0) {
                if (((n >>> 1) & 1) == 0) {
                    n--;
                } else {
                    n++;
                }
            } else {
                n >>>= 1;
            }
            result++;
        }
        return result;
    }
}

Leetcode: Bitwise AND of Numbers Range

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之间有任何数在这一位上等于0，那么此位的and结果就等于0.因此只有当m和n相等的时候才能保证中间的每一个数都相等。[m, n]范围的按位与的结果为m与n的公共“左边首部（left header）”

public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
    	int shifted = 0;
        while (m != n) {
        	m >>= 1;
        	n >>= 1;
        	shifted++;
        }
        return m << shifted;
    }
}

Lintcode: Binary representation

精确的解法应该是用BigDecimal，但是由于Lintcode里的解法是用Double，以下解法在输入为0.6418459415435791的时候和答案不一致。要像通过lintcode，需要将BigDecimal换成double，见Solution 2.

public String binaryRepresentation(String n) {
    	if (n == null || n.length() == 0) {
    		return n;
    	}
        String[] parts = n.split("\\.");
        StringBuilder sb = new StringBuilder();
        int first = Integer.parseInt(parts[0]);
        boolean isNeg = first < 0;
        if (first == Integer.MIN_VALUE) {
        	for (int i = 0; i < 32; i++) {
        		sb.append("1");
        	}
        } else {
        	first = Math.abs(first);
        	while (first != 0) {
        		sb.insert(0, first & 1);
        		first >>= 1;
        	}
        }
        if (sb.length() == 0) {
            sb.append("0");
        }
        //handle the decimal part
        if (parts.length == 2 && Long.parseLong(parts[1]) != 0) {
        	sb.append(".");
        	BigDecimal value = new BigDecimal("0." + parts[1]);
        	Set<BigDecimal> store = new HashSet<BigDecimal>();
        	while (value.compareTo(BigDecimal.ZERO) > 0) {
        		if (sb.substring(sb.indexOf(".") +1).length() > 32 || store.contains(value))  {
        			return "ERROR";
        		}
        		store.add(value);
        		System.out.println(value);
        		if (value.compareTo(new BigDecimal(0.5)) >= 0) {
        			sb.append("1");
        			value = value.multiply(BigDecimal.valueOf(2)).subtract(BigDecimal.ONE);
        		} else {
        			sb.append("0");
        			value = value.multiply(BigDecimal.valueOf(2));
        		}
        	}
        }
        if (isNeg == true) {
        	sb.insert(0, "-");
        }
        return sb.toString();
    }

Solution 2: 其实是错误的，但是lintcode只接受这个答案

import java.math.BigDecimal;
public class Solution {
    /**
     *@param n: Given a decimal number that is passed in as a string
     *@return: A string
     */
    public String binaryRepresentation(String n) {
    	if (n == null || n.length() == 0) {
    		return n;
    	}
        String[] parts = n.split("\\.");
        StringBuilder sb = new StringBuilder();
        int first = Integer.parseInt(parts[0]);
        boolean isNeg = first < 0;
        if (first == Integer.MIN_VALUE) {
        	for (int i = 0; i < 32; i++) {
        		sb.append("1");
        	}
        } else {
        	first = Math.abs(first);
        	while (first != 0) {
        		sb.insert(0, first & 1);
        		first >>= 1;
        	}
        }
        if (sb.length() == 0) {
            sb.append("0");
        }
        //handle the decimal part
        if (parts.length == 2 && Long.parseLong(parts[1]) != 0) {
        	sb.append(".");
        	BigDecimal value = new BigDecimal("0." + parts[1]);
        	double v2 = Double.parseDouble("0." + parts[1]);
        	Set<BigDecimal> store = new HashSet<BigDecimal>();
        	Set<Double> store2 = new HashSet<>();
        	//while (value.compareTo(BigDecimal.ZERO) > 0) {
        	while (v2 > 0) {
        		//if (sb.substring(sb.indexOf(".") +1).length() > 32 || store.contains(value)) {
        		if (sb.substring(sb.indexOf(".") +1).length() > 32 || store2.contains(v2)) {
        			return "ERROR";
        		}
        		store.add(value);
        		store2.add(v2);
        		//System.out.println(value);
        		//System.out.println("double: " + v2);
        		//if (value.compareTo(new BigDecimal(0.5)) >= 0) {
        		if (v2 >= 0.5) {
        			sb.append("1");
        			//value = value.multiply(BigDecimal.valueOf(2)).subtract(BigDecimal.ONE);
        			v2 = v2 * 2 - 1;
        		} else {
        			sb.append("0");
        			//value = value.multiply(BigDecimal.valueOf(2));
        			v2 = v2*2;
        		}
        	}
        }
        if (isNeg == true) {
        	sb.insert(0, "-");
        }
        return sb.toString();
    }
}

Leetcode: Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return Integer.MAX_VALUE;
        }
        
        boolean neg = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        long result = 0;
        while (a >= b) {
            long tmp = 0;
            long b2 = b;
            while (b2 <= a) {
                tmp = tmp == 0 ? 1 : tmp << 1;
                b2 = b2 << 1;
            }
            b2 = b2 >> 1;
            a = a - b2;
            result += tmp;
        }
        if (result >= Integer.MAX_VALUE) {
            result = neg == true? Integer.MIN_VALUE: Integer.MAX_VALUE;
        } else if (neg == true) {
            result = -result;
        }
        return (int)result;
    }
}

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Solution 1：基础办法，右移31次。

public class Solution {
    public long reverseBits(long n) {
        long res = 0;
        for (int i = 0; i < 31; i++) {
        	res |=  n & 1;
        	res <<= 1;
        	n >>= 1;
        }
        res |=  n & 1;
        return res;
    }
}

Solution 2:用到了swap bits的办法，函数swapBits(int n, int i, int j)经常会被用到，用于交换一个int在index i和j的数。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        for (int i = 0; i < 16; i++) {
			n = swapBits(n, i, 32 - i - 1);
		}
		return n;
	}
	
	public int swapBits(int n, int i, int j) {
		int a = (n >> i) & 1;
		int b = (n >> j) & 1;
		if ((a ^ b) != 0) {
			return n ^= (1 << i) | (1 << j);
		}
		return n;
	}
}

Leetcode & Lintcode: Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

Solution 1: TLE

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                res++;
            }
            n >>= 1;
        }
        return res;
    }
}

上面这种做法在n=2147483648 (10000000000000000000000000000000) 的时候会超时,因为需要右移32次。需要注意的时如果想把一个数最右边为1的那一位设成0，用n &= n – 1即可。
Solution 2:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            res++;
            n = n & (n-1);
        }
        return res;
    }
}

Single Number III

In an array, all numbers in the array repeat twice except two numbers, which repeat only once.

Assume all the numbers are placed randomly. Find the 2 numbers.

思路：先将所有的数异或，得到的将是x和y以后之后的值n。 找到这个数n的为1的某一位（为了方便就取最右边为1的一位， n & ~(n-1)，再将这一位为1的数异或，其余的数异或，得到的就是x和y的值。

public int[] singleNumberIII(int[] nums) {
  int n = 0;
  for (int num : nums) {
    n ^= num;
  }
  n = n & ~(n-1);
  int[] res = new int[2];
  for (int num : nums) {
    if (num & n) {
      res[0] ^= num;
    } else {
      res[1] ^= num;
    }
  }
  return res;
}

Repeated DNA Sequences

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”].

最直接的想法是用一个hashset来存放每个见过的string，但是这样会memory limit exceeded.
Solution 1：用rolling hash对每个长度为10的字符串算出一个hash value。

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> result = new HashSet<String>();
        if (s == null || s.length() < 10) {
            return new ArrayList<String>();
        }
        int targetHash = 0, resHash = 0, base = 7, multiplies = 1;
        for (int i = 0; i < 10; i++) {
            targetHash = targetHash * base + s.charAt(i);
            multiplies *= base;
        }
        multiplies /= base;
        Set<Integer> set = new HashSet<Integer>();
        set.add(targetHash);
        for (int i = 1; i + 10 <= s.length(); i++) {
            targetHash = (targetHash - multiplies * s.charAt(i-1)) * base + s.charAt(i + 9);
            if (set.contains(targetHash)) {
                result.add(s.substring(i, i+10));
            } else {
                set.add(targetHash);
            }
        }
        return new ArrayList<String>(result);
    }
}

Solution 2：由于字符串里只有四种字符，因此每个字符用2 bits就可以表示，10个字符即20 bits，一个integer即可表示成功。

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);
        if (s == null || s.length() < 10) {
            return new ArrayList<String>();
        }
        Set<Integer> unique = new HashSet<Integer>();
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i + 10 <= s.length(); i++) {
            int value = 0;
            for (int index = i; index < i+10; index++) {
                value = (value << 2) | map.get(s.charAt(index));
            }
            if (set.contains(value) && !unique.contains(value)) {
                result.add(s.substring(i, i+10));
                unique.add(value);
            } else {
                set.add(value);
            }
        }
        return result;
    }
}