Common Techniques(Java Code Examples)
Determine parity
1
2
| boolean idOdd=(n&1)==1;
boolean idEven=(n&1)==0;
|
Mutiply and divide by powers of 2(watch out for overflow)
1
2
| int doubleVal=n<<1;
int halfVal=n>>1;
|
Swap two numbers(without using a temperary varible)
1
2
3
4
| int a=5,b=3;
a^=b;
b^=a;
a^=b;
|
Get the absolute value(avoid possible negative overflow with Math.abs)
1
2
3
4
5
6
| // 1.
int abs=(n^(n>>31))-(n>>31);
// 2.
int mask=n>>31;
int abs=(n+mask)^mask;
|
Check if a number is a power of 2
1
| boolean isPowerOfTwo=(n>0)&&((n&(n-1))==0);
|
Clear the least significant 1 bit
Get the least significant 1 bit(lowbit)
Count the number of 1s in binary(Brian Kernighan’s algorithm)
1
2
3
4
5
| int count=0;
while(n!=0){
n&=(n-1);
count++;
}
|
Check if the signs are the same
1
| boolean sameSign=((a^b)>=0);
|
Module a power of 2(equivalent to n%m,where m is a power of 2)
Notes in Java
Shift length modulo operation
1
2
3
| int x=1;
x<<32;
x>>33;
|
The effect of unsigned right shift »> on negative numbers
1
2
| int negative=-1;
System.out.println(negative>>>1);
|
Operator precedence
During the bitwise operations,byte,short,and char are automotically promoted to int,and the result is also int.Therefore,after shifting a byte left and assigning it back,a cast is required.
Bitmask and State Management in Java
1
2
3
4
5
6
7
8
9
10
| public static final int READ=1<<0;
public static final int WRITE=1<<1;
public static final int EXEC=1<<2;
int permissions= READ | WRITE ;
if((permissions & READ)!=0) { ... }
permissions|=EXEC;
permissions&=~READ;
|
LeetCode
136.Number that appears only once
The XOR operation satisfies: a^a=0,a^0=a.
1
2
3
4
5
6
7
8
9
| class solution{
public int singleNumber(int[] nums){
int res=nums[0];
for(int i=1;i<nums.length;i++){
res^nums[i];
}
return res;
}
}
|
137.Number that appears only once II
Method 1:Bit-by-bit counting(32-bit)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class solution{
public int singleNumber(int[] nums){
int res=0;
for(int i=0;i<32;i++){
int cnt=0;
for(int num:nums){
cnt+=(num>>i)&1;
}
cnt%=3;
res|=(cnt<<i);
}
return res;
}
}
|
Mathod 2: Finite State Machine
1
2
3
4
5
6
7
8
9
10
| class solution{
public int singleNumber(int[] nums){
int ones=0,twos=0;
for(int num:nums){
ones=(ones^num)&~twos;
twos=(twos^num)&~ones;
}
return ones;
}
}
|
Method 3: Common
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class solution{
public int singleNumber(int[] nums){
Map<Integer,Integer> map=new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
if(entry.getValue()==1){
return entry.getKey();
}
}
return -1;
}
}
|
260.Number that appears only once III
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class solution{
public int[] singleNumber(int[] nums){
int xor=0;
for(int num:nums){
xor^=num;
}
int mask=xor&-xor;
int a=0,b=0;
for(int num:nums){
if((num&mask)==0){
a^=num;
}else{
b^=num;
}
}
return new int[]{a,b};
}
}
|
268.Missing Number
1
2
3
4
5
6
7
8
9
10
11
12
13
| class solution{
public int missingNumber(int[] nums){
int xor=0;
int n=nums.length;
for(int i=0;i<=n;i++){
xor^=i;
}
for(int num:nums){
xor^=num;
}
return xor;
}
}
|
The Set Mismatch
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class solution{
public int[] findErrorNums(int[] nums){
int n=nums.length;
int xor=0;
for(int i=0;i<=n;i++){
xor^=i;
}
for(int num:nums){
xor^=num;
}
int mask=xor^-xor;
int a=0,b=0;
for(int i=0;i<=n;i++){
if((num&mask)!=0){
a^=i;
}else{
b^=i;
}
}
for(int num:nums){
if((num&mask)!=0){
a^=num;
}else{
b^=num;
}
}
for(int num:nums){
if(num==0){
return new int[]{a,b};
}
}
return new int[]{b,a};
}
}
|
421.Maximum XOR of Two Numbers in an Array
Method 1: Trie(Prefix Tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class solution{
class TrieNode{
TrieNode[] children=new TrieNode[2];
}
public int findMaximumXOR(int[] nums){
TrieNode root=new TrieNode();
for(int num:nums){
for(int i=31;i>=0;i--){
int bit=(num>>i)&i;
if(node.children[bit]==null){
node.children[bit]=new TrieNode();
}
node=node.children[bit];
}
}
int max=0;
for(int num:nums){
TrieNode node=root;
int cur=0;
for(int i=31;i>=0;i--){
int bit=(num>>i)&i;
int target=1-bit;
if(node.children[target]!=nulll){
cur|=(1<<i);
node=node.children[target];
}else{
node=node.children[bit];
}
}
max=Math.max(max,cur);
}
return max;
}
}
|
Method 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class solution{
public int findMaximumXOR(int[] nums){
int max=0,mask=0;
for(int i=31;i>=0;i--){
mask|=(1<<i);
Set<Integer> set=new HashSet<>();
for(int num:nums){
set.add(num&mask);
}
int candidate=max|(1<<i);
for(int prefix:set){
if(set.contains(prefix^candidate)){
max=candidate;
break;
}
}
}
return max;
}
}
|
231.Power of 2
1
2
3
4
5
| class solution{
public boolean isPowerOfTwo(int n){
return (n>0)&&(n&(n-1)==0);
}
}
|
191.Number of 1 Bits
1
2
3
4
5
6
7
8
9
10
| class solution{
public int hamminWeight(int n){
int count=0;
while(n!=0){
n&=n-1;
count++;
}
return count;
}
}
|
338.Counting Bits
Method 1:
1
2
3
4
5
6
7
8
9
| class solution{
public int[] countBits(int n){
int[] ans=new int[n+1];
for(int i=0;i<=n;i++){
ans[i]=Integer.bitCount(i);
}
return ans;
}
}
|
Mathod 2:
1
2
3
4
5
6
7
8
9
| class solution{
public int[] countBits(int n){
int[] dp=new int[n+1];
for(int i=1;i<=n;i++){
dp[i]=dp[i>>i]+(i&1);
}
return dp;
}
}
|
Method 3:
1
2
3
4
5
6
7
8
9
| class solution{
public int[] countBits(int n){
int[] dp=new int[n+1];
for(int i=1;i<=n;i++){
dp[i]=dp[i&(i-1)+1];
}
return dp;
}
}
|
201.Bitwise AND of Numbers Range
Method 1:
1
2
3
4
5
6
7
8
9
10
11
| class solution{
public int rangeBitwiseAnd(int left,int right){
int shift=0;
while(left<right){
left>>=1;
right>>=1;
shift++;
}
return left<<shift;
}
}
|
Method 2:
1
2
3
4
5
6
7
8
| class solution{
public int rangeBitwiseAnd(int left,int right){
while(left<right){
right&=(right-1);
}
return right;
}
}
|
461.Hamming Distance
Method 1:
1
2
3
4
5
| class solution{
public int hammingDistance(int x,int y){
return Integer.bitCount(x^y);
}
}
|
Method 2:
1
2
3
4
5
6
7
8
9
10
11
| class solution{
public int hammingDistance(int x,int y){
int xor=x^y;
int count=0;
while(xor!=0){
count+=xor&1;
xor>>=1;
}
return count;
}
}
|
Method 3: Brian Kernighan
1
2
3
4
5
6
7
8
9
10
11
| class solution{
public int hammingDistance(int x,int y){
int xor=x^y;
int count=0;
while(xor!=0){
xor&=(xor-1);
count++;
}
return count;
}
}
|
78.Subset
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class solution{
public List<List<Integer>> subsets(int[] nums){
List<List<Integer>> res=new ArrayList<>();
int n=nums.length;
int total=1<<n;
for(int mask=0;mask<total;mask++){
List<Integer> subset=new ArrayList<>();
for(int i=0;i<n;i++){
if((mask&(1<<i))!=0){
subset.add(nums[i]);
}
}
res.add(subset);
}
return res;
}
}
|
1879.Sum of Minimum XOR Values of Two Arrays
Method 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class solution{
public int minimumXORSum(int[] num1,int[] num2){
int n=num1.length;
int size=1<<n;
int[] dp=new int[size];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0]=0;
for(int mask=0;mask<size;mask++){
if(dp[mask]==Integer.MAX_VALUE) continue;
int cnt=Integer.bitCount(mask);
if(cnt==n) continue;
for(int j=0;j<n;j++){
if((mask&(1<<j))==0){
int newMask=mask|(1<<j);
int val=dp[mask]+(num1[cnt]^num2[j]);
if(val<dp[newMask]){
dp[newMask]=val;
}
}
}
}
return dp[size-1];
}
}
|
Method 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class solution{
public int minimumXORSum(int[] num1,int[] num2){
int n=num1.length;
int size=1<<n;
int INF=0x3f3f3f3f;
int[][] dp=new int[n][size];
for(int i=0;i<n;i++){
Arrays.fill(dp[i],INF);
}
for(int j=0;j<n;j++){
dp[0][1<<j]=num1[0]^num2[j];
}
for(int i=1;i<n;i++){
for(int mask=0;mask<size;mask++){
if(Integer.bitCount(mask)!=i+1) continue;
for(int j=0;j<n;j++){
int prevMask=mask^(1<<j);
if(dp[i-1][prevMask]!=INF){
dp[i][mask]=Math.min(dp[i][mask],
dp[i-1][prevMask]+(num1[i]^num2[j]));
}
}
}
}
return dp[n-1][size-1];
}
}
|
371.Sum of Two Integers
1
2
3
4
5
6
7
8
9
10
| class solution{
public int getSum(int a,int b){
while(b!=0){
int carry=(a&b)<<1;
int a=a^b;
b=carry;
}
return a;
}
}
|
1486.Array XOR Operation
Method 1:
1
2
3
4
5
6
7
8
9
| class solution{
public int xorOperation(int n,int start){
int ans=0;
for(int i=0;i<n;i++){
ans^=(start+2*i);
}
return ans;
}
}
|
Method 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class solution{
public int xoroperation(int n,int start){
int s=start>>1,e=n&start&1;
int ret=sumXor(s-1)^sumXor(s+n-1);
return ret<<1 | e;
}
public int sumXor(int x){
if(x%4==0){
return x;
}
if(x%4==1){
return 1;
}
if(x%4==2){
return x+1;
}
return 0;
}
}
|
