# Week 9: Bits & Sorts

#### Intro

Convert between the binary (base 2), decimal (base 10), and hexadecimal (base 16)

- Example representing the number 38:
- Base 2: 0010 0110
- Base 10: 38
- Base 16: 26

#### Integer Data Types

`int`

vs`long`

data types`int`

is 32-bit, taking up 4 bytes of memory- Stores a range between
`[–2,147,483,648, 2,147,483,647]`

numbers.

- Stores a range between
`long`

is 64-bit, taking up 8 bytes of memory- Stores a range between
`[–9,223,372,036,854,775,808, 9,223,372,036,854,775,807]`

numbers.

- Stores a range between

- The number range provided for
`int`

and`long`

are*signed*integers. - What would the range be if they were
*unsigned*integers?

#### Bitwise Operations

Name | Symbol | Usage | What it does |
---|---|---|---|

`AND` |
`&` |
`a & b` |
Returns `1` only if both the bits are `1` |

`OR` |
`\|` |
`a \| b` |
Returns `1` only if one of the bits is `1` |

`XOR` |
`^` |
`a ^ b` |
Returns `0` if both the bits are the same, else `1` |

`NOT` |
`~` |
`~a` |
Returns the complement of a bit. Ex. `1` ’s complement is `0` |

`LEFT SHIFT` |
`<<` |
`a << n` |
Shifts `a` towards left by `n` digits |

`RIGHT SHIFT` |
`>>` |
`a >> n` |
Shifts `a` towards right by `n` digits |

- In Java, all integer data types are signed.
`<<`

is arithmetic shift (signed)`<<<`

is logical shift (unsigned)

- What are bit masks?

#### Resources

- https://www.tutorialspoint.com/difference-between-int-and-long
- https://www.freecodecamp.org/news/data-types-in-java/
- https://www.baeldung.com/java-bitwise-operators

### 1) Check if Bitwise OR Has Trailing Zeros

You are given an array of positive integers `nums`

.

You have to check if it is possible to select two or more elements in the array such that the bitwise `OR`

of the selected elements has at least one trailing zero in its binary representation.

For example, the binary representation of `5`

, which is `"101"`

, does not have any trailing zeros, whereas the binary representation of `4`

, which is `"100"`

, has two trailing zeros.

Return `true`

if it is possible to select two or more elements whose bitwise `OR`

has trailing zeros, return `false`

otherwise.

**Example 1:**

```
Input: nums = [1,2,3,4,5]
Output: true
Explanation: If we select the elements 2 and 4, their bitwise OR is 6, which has the binary representation "110" with one trailing zero.
```

**Example 2:**

```
Input: nums = [2,4,8,16]
Output: true
Explanation: If we select the elements 2 and 4, their bitwise OR is 6, which has the binary representation "110" with one trailing zero.
Other possible ways to select elements to have trailing zeroes in the binary representation of their bitwise OR are: (2, 8), (2, 16), (4, 8), (4, 16), (8, 16), (2, 4, 8), (2, 4, 16), (2, 8, 16), (4, 8, 16), and (2, 4, 8, 16).
```

**Example 3:**

```
Input: nums = [1,3,5,7,9]
Output: false
Explanation: There is no possible way to select two or more elements to have trailing zeros in the binary representation of their bitwise OR.
```

*Constraints:*

`2 <= nums.length <= 100`

`1 <= nums[i] <= 100`

### 2) Convert a Number to Hexadecimal

Given a positive integer `num`

, return a string representing `num`

in hexadecimal.

All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for when the input is zero.

**Example 1:**

```
Input: num = 26
Output: "1a"
```

**Example 2:**

```
Input: num = 2
Output: "2"
```

*Constraints:*

`0 <= num <= 2^31 - 1`

### 3) Bitwise AND of Numbers Range

Given two integers `left`

and `right`

that represent the range `[left, right]`

, return the bitwise AND of all numbers in this range, inclusive.

**Example 1:**

```
Input: left = 5, right = 7
Output: 4
Explanation: The bitwise AND of all numbers in the range is 4:
5: 101
6: 110
7: 111
100 = 4
```

Example 2:

```
Input: left = 0, right = 0
Output: 0
```

Example 3:

```
Input: left = 1, right = 2147483647
Output: 0
```

*Constraints*

`0 <= num <= 2^31 - 1`

### 4) Gray Code

An **n-bit gray code sequence** is a sequence of `2^n`

integers where:

- Every integer is in the
**inclusive**range`[0, (2^n) - 1]`

, - The first integer is
`0`

, - An integer appears
**no more than once**in the sequence, - The binary representation of every pair of
**adjacent**integers differs by**exactly one bit**, and - The binary representation of the
**first**and**last**integers differs by**exactly one bit**.

Given an integer `n`

, return any valid **n-bit gray code sequence**.

**Example 1:**

```
Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit
```

**Example 2:**

```
Input: n = 1
Output: [0,1]
```

**Constraints:**

`1 <= n <= 16`

*Fun fact:* Gray Code can also be used to solve the Towers of Hanoi problem (pg. 39-47).

#### 4.5) Circular Permutation in Binary Representation

*Optional problem*

Given 2 integers `n`

and `start`

. Your task is return any permutation `p`

of `(0,1,2.....,2^n -1)`

such that:

`p[0] = start`

`p[i]`

and`p[i+1]`

differ by only one bit in their binary representation.`p[0]`

and`p[2^n -1]`

must also differ by only one bit in their binary representation.

**Example 1:**

```
Input: n = 2, start = 3
Output: [3,2,0,1]
Explanation: The binary representation of the permutation is (11,10,00,01).
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]
```

**Example 2:**

```
Input: n = 3, start = 2
Output: [2,6,7,5,4,0,1,3]
Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).
```

*Constraints:*

`1 <= n <= 16`

`0 <= start < 2 ^ n`