Binary, Decimal, and Hexadecimal

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

  • 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

ghetto fix

  • In Java, all integer data types are signed.
    • << is arithmetic shift (signed)
    • <<< is logical shift (unsigned)
  • What are bitwise 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) Count Bits

Write a function that takes an unsigned integer and return the number of 1 bits it has (also known as the Hamming weight).

Input: 0000 1011
Output: 3

Explanation: The input binary string 0000 1011 has a total of three 1bits.

Input: 1000 0000
Output: 1

Explanation: The input binary string 1000 0000 has a total of one 1 bit.

Input: 0010 0000
Output: 1

Explanation: The input binary string 0010 0000 has a total of one 1 bit.

2) Swap Bits

Write a function that swaps the ith and jth bit of a given long.

Input: 100000
Input (a): 1
Input (b): 6
Output: 000001

Input: 1111
Input (a): 1
Input (b): 4
Output: 1111

3) Binary Number with Alternating Bits

Given a positive integer, check whether it has alternating bits (if two adjacent bits will always have different values).

Input: n = 5
Output: true

Explanation: The binary representation of 5 is 101, thus it is alternating.

Input: n = 7
Output: false

Explanation: The binary representation of 7 is 111, thus it is not alternating.

Input: n = 10
Output: true

Explanation: The binary representation of 10 is 1010, thus it is alternating.

Input: n = 17
Output: false

Explanation: The binary representation of 17 is 10001, thus it is not alternating.

  • (BONUS) How would it work with negative numbers?
  • You would have to determine if you want to count the leading bit (negative sign) as part of the alternating pattern.
    • If so, then you need to use logical shift (>>>)
    • If not, then you need to use arithmatic shift (>>)

4) Decode XORed Permutation

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1].

  • For example, if perm = [1,3,2], then encoded = [2,1].

Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

Input: encoded = [3,1]
Output: [1,2,3]

Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

Input: encoded = [6,5,4,6]
Output: [2,4,1,5,3]