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.

Trial Problems

1) Christmas Lights Show

You are given a string of Christmas lights respresented with a single binary number called lights, and a String array called commands that changes which lights turn and off. Return the final binary number representing the Christmas lights.

Commands:

  • “alternate”: Lights that are on 1 turn off 0, and lights that are off 0 turn on 1
  • “shift right”: lights shift to the right, the rightmost light overflows to the left side
  • “shift left”: lights shift to the left, the leftmost light overflows to the right side
Input: 
lights = 10 1010 1010
commands = ["shift left", "alternate", "shift right"]

Output: 01 0101 0101

Step-by-step:
10 1010 1010
01 0101 0101 <- shift left
10 1010 1010 <- alternate
01 0101 0101 <- shift right

Notes:

  • You may limit the size of the binary number to 10 bits
  • You may instead return each intermediary step as an array of binary numbers

2) Binary Sequencing

Given two int in binary num and sequence, return the number of occurences sequence appears in nums.

Input:
num = 1111 1111 1111 1111 1111 1111 1111 1111 = 11111111111111111111111111111111
sequence = 1

Output: 32

Input:
num = 1111 1111 1111 1111 1111 1111 1111 1111 = 11111111111111111111111111111111
sequence = 11

Output: 31

Notes:

  • Try int num = 0xffffffff or int num = -1
  • What would those be in binary?