Java has 8 primitive data types, the following list sorts them according to the memory size.
boolean (1 bit true or false),
byte (8 bits integers),
short (16 bits integers), char (16 bits characters),
int (32 bits integers), float (32 bits single-precision real numbers,
long (64 bits integers), double (64 bits double-precision real numbers)
bit shift >>, <<.
8 >> 2, shift 8 right for 2 bits, it is equal to (8/2)/2 = 2
it is easier to understand the right shift if we use binary presentation, int 8 is binary 0b1000, the 0b1000>>2 will yield a binary number 0b10. The 1 in 1000 moves right 2 bits, we get 0010.
Integer.toBinaryString(0b1000>>2)
8 << 2, shift 8 left for 2 bits, it is equal to 8*2*2=32
Integer.toBinaryString(0b1000<<2) will gives us "100000" with is 32.
For the same rule, 8>>1 is 4, 8>> 3 is 1, 8 << 1 is 16, 8 << 3 is 64.
Now we understood that << and >> are the alternative way of doing /2 and *2. These operations are more useful than that.
bitwise and or xor not: &, |, ^, ~
& is often used as a mask to get a certain value in a range.
We commonly get the last bit, the last 8 bits for an ASCII character, or the last 16 bits for a Unicode character.
Example:
demo>vi Solution.java
demo>javac Solution.java
demo>
demo>cat Solution.java
class Solution {
public static void main(String[] args) {
int i = 1<<3; //8
int j = (1<<24) + (1<<16) + (1<<8) + (1 << 5) + 1; //a 32 bits integer that has 1 on all 4 bytes.
char c = 'A';
System.out.println("get last 1 bit");
System.out.println(Integer.toBinaryString(i & 0b1));
System.out.println(Integer.toBinaryString(i & 0x1));
System.out.println(Integer.toBinaryString(i >> 3 & 0b1));
System.out.println(Integer.toBinaryString(i >> 3 & 0x1));
System.out.println("get last 4 bits, 0b1111 == 0f");
System.out.println(Integer.toBinaryString(i & 0b1111));
System.out.println(Integer.toBinaryString(i & 0xf));
System.out.println(Integer.toBinaryString(1<<4 & 0b1111));
System.out.println(Integer.toBinaryString(1<<3 & 0xf));
System.out.println();
System.out.println("get last 8 bits, 0xff get a byte or an ascii character");
System.out.println(Integer.toBinaryString(c & 0xff));
System.out.println("ascii value:"+(c & 0xff));
System.out.println("convert to Ascii char:"+(char)(c & 0xff));
System.out.println("encode an integer as 4 ascii char string");
System.out.println("j="+ j + ", binary as "+Integer.toBinaryString(j));
char[] chars = new char[4];
for(int m = 0; m < 4; m++) {
chars[3-m] = (char)(j >> (m*8) & 0xff);
}
String encoded = new String(chars);
System.out.println("encoded j as 4 ascii char (may not printable) as: " + encoded);
int k = 0;
for(char ch : encoded.toCharArray()) {
k = (k<<8) + (int)(ch);
}
System.out.println("decoded as " + k);
System.out.println();
System.out.println("get last 16 bits, 0xffff get 2 bytes or a unicode character");
System.out.println("convert to 16 bits unicode char:"+(char)(c & 0xffff));
System.out.println("encode an integer as 2 unicode char string");
System.out.println("j="+ j);
chars = new char[2];
chars[0] = (char)(j & 0xffff);
chars[1] = (char)(j >> 16 & 0xffff);
encoded = new String(chars);
System.out.println("encoded j as 2 unicode char (may not printable) as: " + encoded);
k = (chars[1] << 16) + (int)chars[0];
System.out.println("decoded as " + k);
}
}
demo>
demo>java Solution
get last 1 bit
0
0
1
1
get last 4 bits, 0b1111 == 0f
1000
1000
0
1000
get last 8 bits, 0xff get a byte or an ascii character
1000001
ascii value:65
convert to Ascii char:A
encode an integer as 4 ascii char string
j=16843041, binary as 1000000010000000100100001
encoded j as 4 ascii char (may not printable) as: !
decoded as 16843041
get last 16 bits, 0xffff get 2 bytes or a unicode character
convert to 16 bits unicode char:A
encode an integer as 2 unicode char string
j=16843041
encoded j as 2 unicode char (may not printable) as: ġā
decoded as 16843041
demo>
Let's take a look at another example:
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
In order to solve it, we can use a mask for each array element, if the mask value is 1 we include it, otherwise, we don't. [1, 2, 3] has 3 elements, we need 3 bits to mask it. These masks are 0b000, 0b001, 0b010...0b111. We can start from 0b0, keep adding 1 to it until we got 0b111. Then we can exam the mask value of each bit by right shift then &0b1.
demo>javac Solution.java
demo>
demo>cat Solution.java
import java.util.*;
import java.util.stream.*;
class Solution {
public static void main(String...args) {
int[] arr = new int[]{1, 2, 3};
Solution s = new Solution();
s.subsets(arr).stream().forEach(System.out::println);
}
public List<List<Integer>> subsets(int[] nums) {
int N = nums.length; //3
int m = 1 << N;
//N = 3
//n = 3
//m = 1000b
List<List<Integer>> result = new ArrayList<>();
//0 ... 111
//7 - 111
//N = 3
//
for(int i = 0; i < m; i++) {
List<Integer> sub = new ArrayList<>();
//101
for(int j = N - 1; j >= 0; j--) {
if((i >> j & 0b1) == 1)
sub.add(nums[j]); //1, 3
}
result.add(sub);
}
return result;
}
}
demo>
demo>java Solution
[]
[1]
[2]
[2, 1]
[3]
[3, 1]
[3, 2]
[3, 2, 1]
demo>
Besides the mask &, the ^ is also very handy. Given an integer a, a^a = 0. ^ can be used to remove pairs in a list. Look at the following example:
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
The solution is simple:
demo>javac Solution.java
demo>cat Solution.java
class Solution {
public static void main(String...args) {
int[] arr = new int[]{4,1,2,1,2};
System.out.println(singleNumber(arr));
}
public static int singleNumber(int[] nums) {
int result = 0;
for(int i: nums) {
result ^= i;
}
return result;
}
}
demo>java Solution
4
These operators can be used together.
Let's take a look at another example that combines ~, & and ^ to solve problem.
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2]
Output: 3
Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99
We know ^ can eliminate pairs, however 1 and 3 appearance won't make difference with ^. Therefore we need to use ~ and & to introduce dependence between 1st, 2nd and 3rd appearance.
~first & <expression> is a magic expression.
If first already set, it will become a drop mask -- it will set all the relevant bits in <expression> to 0. If first is 0, it is an all pass mask, makes no effect.
For example, we have
an array [1 2 1 2 1 8 2]
let's rearrange it as [ 2 2 2 1 1 1 8] , so that we can focus on the first 3 item group.
first = 0
second = 0
a = 00000010
first time see a:
first = ~second & (first ^ a) = first ^ a = 0 ^ a = a
second = ~first & (second ^ a) = ~first & a = ~a & a = 0
second time see a:
first = ~second & (first ^ a) = first ^ a = a ^ a = 0
second = ~first & (second ^ a) = second ^ a = a
third time see a:
first = ~second & (first ^ a) = ~a & a = 0
second = ~first & (second ^ a) = a ^ a = 0
Now first's value is different at the first and third time we see a, besides, after we process the third a, both first and second is reset to 0. So we got the solution.
demo>javac Solution.java
demo>cat Solution.java
class Solution {
public int singleNumber(int[] nums) {
int first = 0;
int second = 0;
for(int i : nums) {
first = ~second & (first ^ i);
second = ~first & (second ^ i);
}
return first;
}
public static void main(String[] args) {
int[] arr = new int[] {0,1,0,1,0,1,99};
Solution s = new Solution();
System.out.println(s.singleNumber(arr));
}
}
demo>java Solution
99
Let's take a look at another example.
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
Follow up: Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
Example 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.
Example 2:
Input: nums = [-1,0]
Output: [-1,0]
Example 3:
Input: nums = [0,1]
Output: [1,0]
This time, we can use ^ to get rid of all the pairs and get a^b. The question is, how to find the difference between a and b.
x & (-x) is a way to isolate the rightmost 1-bit, i.e. to keep the rightmost 1-bit and to set all the others bits to zero.
say x = 00111111
-x = ~x + 1 = 11000001
x & (-x) = 1
Knowing this fact, we can differentiate a and b.
a ^ b is the difference between a and b, so their rightmost 1-bit has to be different.
As a result, let x = a^b, if a & (-x) is 1, then b & (-x) must be 0.
Now a and b can be differentiated by -(a^b), we have the solution.
demo>javac Solution.java
demo>cat Solution.java
class Solution {
public int[] singleNumber(int[] nums) {
int com = 0;
for(int i : nums) {
com ^= i;
}
int x = com & (-com);
int result = 0;
for(int i : nums) {
if((x & i) != 0)
result ^= i;
}
return new int[]{result, result^com};
}
public static void main(String...args) {
int[] arr = new int[]{1,2,1,3,2,5};
Solution s = new Solution();
int[] x = s.singleNumber(arr);
System.out.println(x[0] + "," + x[1]);
}
}
demo>java Solution
3,5
This way we achieve the goal with O(N) time and O(1) space.
It is worth mentioning that + and - can be replaced by bitwise operations.
For example, for a+b
a = 0b10011010
b = 0b00100111
a ^ b = 0b10111101 -- it is the diff of a and b, so it is a+b except the carry-on bits
(a&b)<<1 will give the carry-on bits
now we need to calculate a^b + (a&b)<<1, we again use the above approach -- calculate the diff bits and carry-on bits. This calculation can be done in a loop until the carry-on bit is 0.
int a = 30;
int b = 20;
int diff = 1;
int carry = 1;
while(carry != 0) {
diff = a^b;
carry = (a&b)<<1;
a = diff;
b = carry;
}
return diff;
similarly for a - b
the diff is a^b
the carry-on bits is ((~a)&b)<<1
int a = 30;
int b = 20;
int diff = 1;
int carry = 1;
while(carry != 0) {
diff = a^b;
carry = ((~a)&b)<<1;
a = diff;
b = carry;
}
return diff;
Sometimes we need to left padding a binary string with 0s, the way of doing that is to use a mask and substring.
demo>javac Solution.java
demo>cat Solution.java
class Solution {
public static void main(String...args) {
int L = 10;
int a = 30;
int mask = 1<<L;
String padded = Integer.toBinaryString(a | mask).substring(1);
System.out.println(padded);
}
}
demo>java Solution
0000011110
Another useful tool is a binary trie.
Our all lowercase letter String trie looks like the following:
class TrieNode {
TrieNode[] links = new TrieNode[26];
boolean isEnd = false;
}
class Trie {
TrieNode root = new TrieNode();
public void insert(String word) {
TrieNode node = root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if(node.links[c - 'a'] != null) {
node.links[c - 'a'] = new TrieNode();
}
node = node.links[c - 'a'];
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if(node.links[c - 'a'] != null) {
node = node.links[c - 'a'];
} else {
return false;
}
}
return node.isEnd;
}
}
For binary trie, we only have 2 characters, 1 and 0.
So we modify the above program:
class TrieNode {
TrieNode[] links = new TrieNode[2];
boolean isEnd = false;
}
node.links[c - '0']
That's it, we can then search binary strings such as 1000100 and 0000101.
For example.
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.
Follow up: Could you do this in O(n) runtime?
Example 1:
Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.
Example 2:
Input: nums = [0]
Output: 0
Example 3:
Input: nums = [2,4]
Output: 6
Example 4:
Input: nums = [8,10,2]
Output: 10
Example 5:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127
We can find O(N) solution with the help of binary trie. We can build a binary trie. Then given any binary string such as 1000110, we can quickly find the max xor from the trie. We start from left most bit and trie root. We want to choose the opposite of 1, so if there is '0' node in trie, we go into that node, otherwise, we have no choice but go into '1' node. Once we reached the leaf node, our pass is the maximun xor value.
demo>javac Solution.java
demo>cat Solution.java
import java.util.*;
import java.util.stream.*;
class Solution {
static class TrieNode {
TrieNode[] links = new TrieNode[2];
boolean isEnd = false;
}
static class Trie {
TrieNode root = new TrieNode();
public void insert(String str) {
TrieNode node = root;
for(int i = 0; i < str.length(); i++) {
if(node.links[str.charAt(i) - '0'] == null) {
node.links[str.charAt(i) - '0'] = new TrieNode();
}
node = node.links[str.charAt(i) - '0'];
}
node.isEnd = true;
}
}
public static void main(String...args) {
int[] arr = new int[]{3,10,5,25,2,8};
Solution s = new Solution();
System.out.println(s.findMaximumXOR(arr));
}
public int findMaximumXOR(int[] nums) {
int max = IntStream.of(nums).max().getAsInt();
int L = Integer.toBinaryString(max).length();
int mask = 1 << L;
List<String> bstr = IntStream.of(nums).mapToObj(
i -> Integer.toBinaryString(i | mask).substring(1))
.collect(Collectors.toList());
Trie root = new Trie();
for(String s : bstr) {
root.insert(s);
}
return bstr.stream()
.mapToInt(i -> maxXor(root.root, i))
.max().getAsInt();
}
private int maxXor(TrieNode node, String b) {
int result = 0;
for(int i = 0; i < b.length(); i++) {
int bit = b.charAt(i) == '0' ? 1 : 0;
if(node.links[bit] != null) {
result = (result << 1) | 1;
node = node.links[bit];
} else {
result = result << 1;
node = node.links[b.charAt(i) - '0'];
}
}
return result;
}
}
demo>java Solution
28
The solution can be futher improved. We can start to calculate the xor values while we are building the trie. We add a new value to the trie, and calculate the max xor with the existing elements in the trie.
