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

Name Symbol Usage What it does Example (a=0b1010, b=0b0011)
AND & a & b Returns 1 only if both the bits are 1 0b0010
OR \| a \| b Returns 1 only if one of the bits is 1 0b1011
XOR ^ a ^ b Returns 0 if both the bits are the same, else 1 0b1001
NOT ~ ~a Returns the complement of a bit. Ex. 1’s complement is 0 0b11111111111111111111111111110101 (-11)
LEFT SHIFT << a << n Shifts a towards left by n bits 0b10100, 0b0110
RIGHT SHIFT >> a >> n Shifts a towards right by n bits 0b0101, 0b0001
  • In Java, all integer data types are signed.
    • >> is arithmetic (signed) shift (fills in with sign bit 0 or 1)
    • >>> is logical (unsigned) shift (fills in with 0)
  • What are bitwise masks?
    • Given an integer number return the integer value of bits 1-4 - 254 = 0b1111 1110, returns 14 = 0b0000 1110
      • Use a “mask” to get the bits… 0b1111 1110 & 0b0000 1111

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]