leetcode questions: Bit

common tricks

`x & (-x) to isolate/get the rightmost 1-bit`

This operation reverts all bits of x except the rightmost 1-bit.

Hence, x and -x have just one bit in common - the rightmost 1-bit. That means that x & (-x) would keep that rightmost 1-bit and set all the other bits to 0.

`x & (x - 1) is a way to set the rightmost 1-bit to zero.`

To subtract 1 means to change the rightmost 1-bit to 0 and to set all the lower bits to 1.

Now AND operator: the rightmost 1-bit will be turned off because 1 & 0 = 0, and all the lower bits as well. Detect Power of Two

The solution is straightforward: Power of two has just one 1-bit. x & (x - 1) sets this 1-bit to zero, and hence one has to verify if the result is zero x & (x - 1) == 0.

language specific

Python

• `num.bit_length()` find the first one
• code
``````class Solution:
def findComplement(self, num):
return ((1 << num.bit_length()) - 1 ) ^ num
``````
• x*2^i = x«i, 1000 « 1 = 2000
• 5«3 = 5*(2^3)
• def bin2dec(string_num):
• return str(int(string_num, 2))
• num to bin string: bin(1234)[2:]
• bin(4) -> 0b1000

Java

`return Integer.bitCount(n);` Number of 1 bits in integer n.

``````class Solution {
public String addBinary(String a, String b) {
return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
}
}
``````

`Integer.highestOneBit()`

• code
``````class Solution {
public int findComplement(int num) {
return (Integer.highestOneBit(num) << 1) - num - 1;
}
}
``````

questions

338. Counting Bits

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
``````
• code
``````class Solution:
def countBits(self, n: int) -> List[int]:
res = [0] * (n + 1)
for i in range(1, n + 1):
res[i] = res[i & (i - 1)] + 1
return res
``````

Given two binary strings a and b, return their sum as a binary string.

Example 1: Input: a = “11”, b = “1” Output: “100”

Example 2: Input: a = “1010”, b = “1011” Output: “10101”

Constraints:

``````1 <= a.length, b.length <= 104
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.
``````
• code
``````class Solution:
def addBinary(self, a, b) -> str:
x, y = int(a, 2), int(b, 2)
while y:
x, y = x ^ y, (x & y) << 1
return bin(x)[2:]
``````

371. Sum of Two Integers

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

• code
``````class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int answer = a ^ b;
int carry = (a & b) << 1;
b = carry;
}

return a;
}
}
``````
• code
``````class Solution:
def getSum(self, a: int, b: int) -> int:

_carry = a & b
a = a ^ b
b = _carry << 1

# for overflow condition like
# -1
#  1
``````

231. Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false. An integer n is a power of two, if there exists an integer x such that n == 2x.

Example 1: Input: n = 1 Output: true Explanation: 20 = 1 Example 2: Input: n = 16 Output: true Explanation: 24 = 16 Example 3: Input: n = 3 Output: false

Constraints:

-231 <= n <= 231 - 1

• code
``````class Solution:
def isPowerOfTwo(self, n: int) -> bool:
while n > 1:
if n % 2 != 0: return False
n = n // 2
return n == 1
``````
• code
``````class Solution(object):
def isPowerOfTwo(self, n):
if n == 0:
return False
return n & (-n) == n
``````
• code
``````class Solution {
public boolean isPowerOfTwo(int n) {
if (n == 0) return false;
long x = (long) n;
return (x & (-x)) == x;
}
}
``````

476. Number Complement

The complement of an integer is the integer you get when you flip all the 0’s to 1’s and all the 1’s to 0’s in its binary representation.

For example, The integer 5 is “101” in binary and its complement is “010” which is the integer 2.Given an integer num, return its complement.

Example 1: Input: num = 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2: Input: num = 1 Output: 0 Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Constraints:

1 <= num < 231

• code
``````class Solution:
def findComplement(self, num):
# bitmask has the same length as num and contains only ones 1...1
# flip all bits
``````
• code
``````class Solution:
def findComplement(self, num: int) -> int:
reverse = []
num_bin = bin(num)
for i in range(2, len(num_bin)):
reverse.append(str(int(num_bin[i]) ^ 1))
return int("".join(reverse), 2)
``````
• code
``````class Solution {
public int findComplement(int num) {
return (Integer.highestOneBit(num) << 1) - num - 1;
}
}
``````
• code
``````class Solution:
def findComplement(self, num):
return ((1 << num.bit_length()) - 1 ) ^ num
``````