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.
    • 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.
  • 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 = 3
Output: [0, 1, 3, 2, 6, 7, 5, 4]

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