Binary Flashcards
Bitwise operations
- Sum of Two Integers
Solved
Medium
Topics
Companies
Given two integers a and b, return the sum of the two integers without using the operators + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = 2, b = 3
Output: 5
Constraints:
-1000 <= a, b <= 1000
class Solution {
public:
int getSum(int a, int b) {
while (b != 0) {
int carry = a & b;
a ^= b; // a = a ^ b;
b = carry «_space;1;
}
return a;
}
};
It is like bitwise operator addition. 1 + 0 = 1 and 1 + 1 = 0 if the addition is 1 + 1 = 0, then carry that 1 to the next highest significant order (most significant). Hence why we are using the shift operator to the left.
- Number of 1 Bits
Solved
Easy
Topics
Companies
Write a function that takes the binary representation of a positive integer and returns the number of
set bits
it has (also known as the Hamming weight).
Example 1:
Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.
Example 2:
Input: n = 128
Output: 1
Explanation:
The input binary string 10000000 has a total of one set bit.
Example 3:
Input: n = 2147483645
Output: 30
Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.
Constraints:
1 <= n <= 231 - 1
Follow up: If this function is called many times, how would you optimize it?
class Solution {
public:
int hammingWeight(int n) {
int counter = 0;
while (n > 0) {
if ((n & 1) == 1) {
counter++;
}
n»_space;= 1;
}
return counter;
}
};
Compare n with the bitwise number 1 and use the bitwise & operator. Bitwise & works like this. When both values are 1 return true. When Both value are 0, or each value is different return false.
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 0
Start from the least significant value, then check if that value is equal to 1. If true increment the counter value. Then shift n to the least significant value until n is zero.
For example:
n = 11
1011 -> 0101 -> 0010 -> 0001 -> 0000
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 –> 0
1 –> 1
2 –> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 –> 0
1 –> 1
2 –> 10
3 –> 11
4 –> 100
5 –> 101
Constraints:
0 <= n <= 105
Follow up:
It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n + 1);
for (int i = 0; i <= n; i++) {
if (i % 2 == 0) {
ans[i] = ans[i / 2];
} else {
ans[i] = ans[i / 2] + 1;
}
}</int></int>
return ans; } };
In computer science you can have only to option 1 or 0. Therefore, in computer science the decimal system is is base 2 instead of base 10. That why we divide the index by 2.
- Missing Number
Solved
Easy
Topics
Companies
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
Constraints:
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
class Solution {
public:
int missingNumber(vector<int>& nums) {
int missing_number = nums.size();
int length = nums.size();
for (int i = 0; i < length; i++) {
missing_number ^= current_number;
missing_number ^= nums[i];
}
return missing_number;
}
};</int>
i = current_number
It is a alternation between adding and subtracting numbers. missing_number ^ i is the equivalency of missing_number - i. While missing_number ^ nums[i], add the corresponding numbers. missing_number ^ nums[i] is is the equivalency of missing_number + i.
- Reverse Bits
Solved
Easy
Topics
Companies
Reverse bits of a given 32 bits unsigned integer.
Note:
Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.
Example 1:
Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:
Input: n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
Constraints:
The input must be a binary string of length 32
Follow up: If this function is called many times, how would you optimize it?
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t reverse = 0;
int bit_position = 31;
while (n > 0) {
reverse = reverse | (n & 1) «_space;bit_position;
n»_space;= 1; // n = n»_space; 1;
–bit_position;
}
return reverse;
}
};
