The first part is related to Java bit arithmetic. Although we don’t use bit arithmetic very often in daily development, it can be greatly improved in terms of performance. Here are some tips for bitwise operations:
Offer II 001. Integer division
Dry:
Given two integers A and b, find the quotient of their division, a/b, without using the multiplication ‘*’, the division ‘/’, and the complementary sign ‘%’.
Note:
The result of integer division should truncate the decimal part, for example, TRUNCate (8.345) = 8 and TRUNCate (-2.7335) = -2. Assume that our environment can store only 32-bit signed integers with values in the range of [−231, 231−1]. In this case, 231 − 1 is returned if the division result overflows
Example 1:
Input: A = 15, b = 2
Output: 7
15/2 = TRUNCate (7.5) = 7
Example 2:
Input: A = 7, b = -3
Output: – 2
7/-3 = truncate(-2.33333..) = 2 –
Example 3:
Input: A = 0, b = 1
Output: 0
Example 4:
Input: A = 1, b = 1
Output: 1.
Analysis:
This problem is mainly to use the addition and subtraction to achieve division, pay attention to the case of 32 overflow, and timeout. I plan to use subtraction to simulate, if you do not do special processing, there will be a timeout, so, need to deal with the iteration step.
Refer to the answer
// Because turning -2147483648 into a positive number is out of bounds, but turning 2147483647 into a negative number is not
// So, we convert both a and b to negative numbers
class Solution {
public int divide(int a, int b) {
if(a == Integer.MIN_VALUE && b == -1) {return Integer.MAX_VALUE;
}
int sign = (a>0)^(b>0)? -1 : 1; // ^ is xOR
if(a>0) a = -a;
if(b>0) b = -b;
int res = 0;
while(a <= b){
int value = b; // A can subtract the maximum of b
int k = 1; // value Contains the number of B's
// 0xC0000000 is a hexadecimal representation of decimal -2^30
// Determine the cause of value > 0xC0000000: ensure that value + value < -2^31 does not overflow
// The reason for this is that 0xC0000000 is half of the minimum value -2^31,
// A cannot be less than -2^31, so value cannot be less than 0xC0000000
// -2^ 31/2 = -2^30
while(value > 0xc0000000 && a < value + value){
value += value;
k += k;
}
a -= value;
res += k;
}
return sign == 1? res: -res; }}Copy the codeKnowledge:
- ^ is xOR operation
- Integer.MAX_VALUE is 2^31-1, integer. MIN_VALUE is -2^31
Offer II 002. Binary addition
Dry:
Given two 01 strings A and B, compute their sum and output it as a binary string.
The input is a non-empty string containing only the digits 1 and 0.
Example 1:
Input: a = “11”, b = “10”
Output: “101”
Example 2:
Input: a = “1010”, b = “1011”
Output: “10101”
Analysis:
To simulate this process, use binary addition. The key is the conversion of char and int.
Refer to the answer
class Solution {
public String addBinary(String a, String b) {
StringBuffer ans = new StringBuffer(); // For string manipulation, use StringBuffer or StringBuilder
int alen = a.length();
int blen = b.length();
int temp = 0; / / carry
int maxLen = Math.max(alen,blen);
for(int i=0; i<maxLen; ++i){
int t1 = i<alen ? (a.charAt(alen-i-1) - '0') : 0;
int t2 = i<blen ? (b.charAt(blen-i-1) - '0') : 0;
int sum = t1 + t2 + temp;
if(sum > 1){
temp = sum/2;
sum = sum%2;
}else{
temp = 0;
}
ans.append((char) (sum + '0'));
}
if(temp ! =0){
ans.append('1');
}
ans.reverse();
returnans.toString(); }}Copy the codeKnowledge:
- Char converted to int,
'4' - '0' = > 4 - Int to char,
4 + '0' = > '4'
Offer II 003. The number of 1’s in the first n digit binary
Dry:
Given a non-negative integer n ****, count the number of 1s in the binary representation of each number between 0 and n and output an array.
Example 1:
Enter: n = 2
Output:,1,1 [0]
Explanation:
0 — > 0
1 — — > 1
2 –> 10
Example 2:
Enter n = 5
Output:,1,1,2,1,2 [0]
Explanation:
0 — > 0
1 — — > 1
2 –> 10
3 –> 11
4 – – > 100
5 – – > 101
Analysis:
The simplest way to do this is to iterate from 0 to n, figure out how many 1’s there are for each I in binary, and then output the result as an array. But this method has a high time complexity of O(n*sizeof(integer)).
Method two is to do it in one scan in linear time O(n). For this problem, we can divide all numbers into odd and even numbers:
If num is odd, the number of 1’s in the binary is the number of the previous binary 1 +1. The current number is odd, which means that the previous number is even, so the last bit of the previous binary must be 0, and the current number is just a 1 added to it. For example, 5(101), the previous number is 4(100), 5 = 4 + 1, plus 1 is the last digit added to the binary.
If num is currently even, the number of ones in the binary is the number of ones in the binary of num/2. This was inspired by bit arithmetic. For example, (1)0001 becomes 2(0010) after moving one place to the left, and 2(0010) becomes 4(0100) after moving one place to the left. The number of 1’s in both of them is the same, but the position is changing.
Refer to the answer
// Method 1:
class Solution {
public int[] countBits(int n) {
int ans[] = new int[n+1];
for (int i=0; i<=n; i++){
ans[i] = count1(i);
}
return ans;
}
public int count1(int n) {
int res = 0;
while(n > 1) {if(n%2! =0){
res++;
}
n = n/2;
}
return n==0 ? 0: ++res; }}// Method 2:
class Solution {
public int[] countBits(int n) {
int ans[] = new int[n+1];
for (int i=0; i<=n; i++){
if(i % 2= =0) {/ / even
ans[i] = ans[i>>1]; // Is equivalent to I /2
}else{ / / odd
ans[i] = ans[i-1] + 1; }}returnans; }}Copy the codeKnowledge:
- A shift of 1 to the left is the same as multiplying the number by 2, and a shift of 2 to the left is the same as multiplying the number by 2 times 2, which is 4. 15<<2=60, which is multiplied by 4. But this conclusion only applies to the case that when the number moves to the left, there is no 1 in the high level discarded by overflow.
- Moving 1 to the right is the same thing as dividing by 2. For example, 4>>2 = 2