## 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

ansof lengthn + 1such that for eachi(0 <= i <= n),ans[i]is the number of1’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
```

### 67. Add Binary

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;
a = answer;
b = carry;
}
return a;
}
}
```

- code

```
class Solution:
def getSum(self, a: int, b: int) -> int:
mask = 0xffffffff
while b & mask:
_carry = a & b
a = a ^ b
b = _carry << 1
# for overflow condition like
# -1
# 1
return (a & mask) if b > mask else a
```

### 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
bitmask = num
bitmask |= (bitmask >> 1)
bitmask |= (bitmask >> 2)
bitmask |= (bitmask >> 4)
bitmask |= (bitmask >> 8)
bitmask |= (bitmask >> 16)
# flip all bits
return bitmask ^ num
```

- 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
```