Bit Manipulation

Definition

Definition

It involves manipulating individual bits within a binary representation of data. This algorithm aims to efficiently perform operations like setting, clearing, toggling, or checking the status of specific bits within binary numbers

Explanation

The algorithm leverages bitwise operators to perform operations directly on individual bits of binary numbers

Guidance

• Setting a Bit
  • to set a specific bit at position pos in an integer num, use the OR operator with a bitmask where only the desired bit is set to 1
    • num |= (1 << pos)
• Clearing a Bit
  • to clear a specific bit at position pos in an integer num, use the AND operator with a bitmask where only the desired bit is set to 0
    • num &= ~(1 << pos)
• Toggling a Bit
  • to toggle a specific bit at position pos in an integer num, use the XOR operator with a bitmask where only the desired bit is set to 1
    • num ^= (1 << pos)
• Checking the Status of a Bit
  • to check if a specific bit at position pos in an integer num is set, use the AND operator with a bitmask where only the desired bit is set to 1
    • (num & (1 << pos)) != 0 will return true if the bit is set, false otherwise

Tips

• be mindful of integer overflow when shifting bits
• ensure to use unsigned integers to avoid issues with signed bit manipulation

Practice

Practice

// Setting a bit at position pos in num
setBit(num, pos):
  return num | (1 << pos)

// Clearing a bit at position pos in num
clearBit(num, pos):
  return num & ~(1 << pos)

// Toggling a bit at position pos in num
toggleBit(num, pos):
  return num ^ (1 << pos)

// Checking if a bit at position pos in num is set
isBitSet(num, pos):
  return (num & (1 << pos)) != 0

Solution

package main

func getBit(number, bitPosition int) int {
    return (number >> bitPosition) & 1
}

func setBit(number, bitPosition int) int {
    return number | (1 << bitPosition)
}

func clearBit(number, bitPosition int) int {
    return number &^ (1 << bitPosition)
}

func updateBit(number, bitPosition, bitValue int) int {
    mask := ^(1 << bitPosition)
    return (number & mask) | (bitValue << bitPosition)
}

func isEven(number int) bool {
    return (number & 1) == 0
}

func isPositive(number int) bool {
    return number >= 0 && (number & 0x80000000) == 0
}

func multiplyByTwo(number int) int {
    return number << 1
}

func divideByTwo(number int) int {
    return number >> 1
}

func switchSign(number int) int {
    return ^number + 1
}

func multiply(a, b int) int {
    if b == 0 {
        return 0
    }
    if b > 0 {
        return a + multiply(a, b-1)
    }
    if b < 0 {
        return -multiply(a, -b)
    }
    return 0
}

func multiplyUnsigned(x, y int) int {
    var result int
    for y > 0 {
        if y&1 == 1 {
            result += x
        }
        x <<= 1
        y >>= 1
    }
    return result
}

func countSetBits(number int) int {
    var count int
    for number != 0 {
        count += number & 1
        number >>= 1
    }
    return count
}

func bitsDiff(a, b int) int {
    var count int
    diff := a ^ b
    for diff != 0 {
        count += diff & 1
        diff >>= 1
    }
    return count
}

func bitLength(number int) int {
    var count int
    for number != 0 {
        count++
        number >>= 1
    }
    return count
}

func isPowerOfTwo(number int) bool {
    return number != 0 && (number&(number-1)) == 0
}

func fullAdder(a, b int) int {
    var carry, result, i int
    for a != 0 || b != 0 || carry != 0 {
        bitA := a & 1
        bitB := b & 1
        sum := bitA ^ bitB ^ carry
        result |= sum << i
        carry = (bitA & bitB) | (bitA & carry) | (bitB & carry)
        a >>= 1
        b >>= 1
        i++
    }
    return result
}

public class BitOperations {

  public static int getBit(int number, int bitPosition) {
    return (number >> bitPosition) & 1;
  }

  public static int setBit(int number, int bitPosition) {
    return number | (1 << bitPosition);
  }

  public static int clearBit(int number, int bitPosition) {
    return number & ~(1 << bitPosition);
  }

  public static int updateBit(int number, int bitPosition, int bitValue) {
    int mask = ~(1 << bitPosition);
    return (number & mask) | (bitValue << bitPosition);
  }

  public static boolean isEven(int number) {
    return (number & 1) == 0;
  }

  public static boolean isPositive(int number) {
    return number >= 0 && (number & 0x80000000) == 0;
  }

  public static int multiplyByTwo(int number) {
    return number << 1;
  }

  public static int divideByTwo(int number) {
    return number >> 1;
  }

  public static int switchSign(int number) {
    return ~number + 1;
  }

  public static int multiply(int a, int b) {
    if (b == 0) {
      return 0;
    }
    if (b > 0) {
      return a + multiply(a, b - 1);
    }
    if (b < 0) {
      return -multiply(a, -b);
    }
    return 0;
  }

  public static int multiplyUnsigned(int x, int y) {
    int result = 0;
    while (y > 0) {
      if ((y & 1) == 1) {
        result += x;
      }
      x <<= 1;
      y >>= 1;
    }
    return result;
  }

  public static int countSetBits(int number) {
    int count = 0;
    while (number != 0) {
      count += number & 1;
      number >>= 1;
    }
    return count;
  }

  public static int bitsDiff(int a, int b) {
    int count = 0;
    int diff = a ^ b;
    while (diff != 0) {
      count += diff & 1;
      diff >>= 1;
    }
    return count;
  }

  public static int bitLength(int number) {
    int count = 0;
    while (number != 0) {
      count++;
      number >>= 1;
    }
    return count;
  }

  public static boolean isPowerOfTwo(int number) {
    return number != 0 && (number & (number - 1)) == 0;
  }

  public static int fullAdder(int a, int b) {
    int carry = 0;
    int result = 0;
    int i = 0;
    while (a != 0 || b != 0 || carry != 0) {
      int bitA = a & 1;
      int bitB = b & 1;
      int sum = bitA ^ bitB ^ carry;
      result |= sum << i;
      carry = (bitA & bitB) | (bitA & carry) | (bitB & carry);
      a >>= 1;
      b >>= 1;
      i++;
    }
    return result;
  }
}

function getBit(number, bitPosition) {
  return (number >> bitPosition) & 1;
}

function setBit(number, bitPosition) {
  return number | (1 << bitPosition);
}

function clearBit(number, bitPosition) {
  return number & ~(1 << bitPosition);
}

function updateBit(number, bitPosition, bitValue) {
  const mask = ~(1 << bitPosition);
  return (number & mask) | (bitValue << bitPosition);
}

function isEven(number) {
  return (number & 1) === 0;
}

function isPositive(number) {
  return number >= 0 && (number & 0x80000000) === 0;
}

function multiplyByTwo(number) {
  return number << 1;
}

function divideByTwo(number) {
  return number >> 1;
}

function switchSign(number) {
  return ~number + 1;
}

function multiply(a, b) {
  if (b === 0) {
    return 0;
  }
  if (b > 0) {
    return a + multiply(a, b - 1);
  }
  if (b < 0) {
    return -multiply(a, -b);
  }
}

function multiplyUnsigned(x, y) {
  let result = 0;
  while (y > 0) {
    if (y & 1) {
      result += x;
    }
    x <<= 1;
    y >>= 1;
  }
  return result;
}

function countSetBits(number) {
  let count = 0;
  while (number) {
    count += number & 1;
    number >>= 1;
  }
  return count;
}

function bitsDiff(a, b) {
  let count = 0;
  let diff = a ^ b;
  while (diff) {
    count += diff & 1;
    diff >>= 1;
  }
  return count;
}

function bitLength(number) {
  let count = 0;
  while (number) {
    count++;
    number >>= 1;
  }
  return count;
}

function isPowerOfTwo(number) {
  return number !== 0 && (number & (number - 1)) === 0;
}

function fullAdder(a, b) {
  let carry = 0;
  let result = 0;
  let i = 0;
  while (a !== 0 || b !== 0 || carry !== 0) {
    const bitA = a & 1;
    const bitB = b & 1;
    const sum = bitA ^ bitB ^ carry;
    result |= sum << i;
    carry = (bitA & bitB) | (bitA & carry) | (bitB & carry);
    a >>= 1;
    b >>= 1;
    i++;
  }
  return result;
}

fun getBit(number: Int, bitPosition: Int): Int {
    return (number shr bitPosition) and 1
}

fun setBit(number: Int, bitPosition: Int): Int {
    return number or (1 shl bitPosition)
}

fun clearBit(number: Int, bitPosition: Int): Int {
    return number and (1 shl bitPosition).inv()
}

fun updateBit(number: Int, bitPosition: Int, bitValue: Int): Int {
    val mask = (1 shl bitPosition).inv()
    return (number and mask) or (bitValue shl bitPosition)
}

fun isEven(number: Int): Boolean {
    return (number and 1) == 0
}

fun isPositive(number: Int): Boolean {
    return number >= 0 && (number and 0x80000000.inv()) == 0
}

fun multiplyByTwo(number: Int): Int {
    return number shl 1
}

fun divideByTwo(number: Int): Int {
    return number shr 1
}

fun switchSign(number: Int): Int {
    return number.inv() + 1
}

fun multiply(a: Int, b: Int): Int {
    return when {
        b == 0 -> 0
        b > 0 -> a + multiply(a, b - 1)
        else -> -multiply(a, -b)
    }
}

fun multiplyUnsigned(x: Int, y: Int): Int {
    var result = 0
    var x = x
    var y = y
    while (y > 0) {
        if (y and 1 == 1) {
            result += x
        }
        x = x shl 1
        y = y shr 1
    }
    return result
}

fun countSetBits(number: Int): Int {
    var count = 0
    var number = number
    while (number != 0) {
        count += number and 1
        number = number shr 1
    }
    return count
}

fun bitsDiff(a: Int, b: Int): Int {
    var count = 0
    var diff = a xor b
    while (diff != 0) {
        count += diff and 1
        diff = diff shr 1
    }
    return count
}

fun bitLength(number: Int): Int {
    var count = 0
    var number = number
    while (number != 0) {
        count++
        number = number shr 1
    }
    return count
}

fun isPowerOfTwo(number: Int): Boolean {
    return number != 0 && (number and (number - 1)) == 0
}

fun fullAdder(a: Int, b: Int): Int {
    var carry = 0
    var result = 0
    var i = 0
    var a = a
    var b = b
    while (a != 0 || b != 0 || carry != 0) {
        val bitA = a and 1
        val bitB = b and 1
        val sum = bitA xor bitB xor carry
        result = result or (sum shl i)
        carry = (bitA and bitB) or (bitA and carry) or (bitB and carry)
        a = a shr 1
        b = b shr 1
        i++
    }
    return result
}

def get_bit(number, bit_position):
    return (number >> bit_position) & 1

def set_bit(number, bit_position):
    return number | (1 << bit_position)

def clear_bit(number, bit_position):
    return number & ~(1 << bit_position)

def update_bit(number, bit_position, bit_value):
    mask = ~(1 << bit_position)
    return (number & mask) | (bit_value << bit_position)

def is_even(number):
    return (number & 1) == 0

def is_positive(number):
    return number >= 0 and (number & 0x80000000) == 0

def multiply_by_two(number):
    return number << 1

def divide_by_two(number):
    return number >> 1

def switch_sign(number):
    return ~number + 1

def multiply(a, b):
    if b == 0:
        return 0
    if b > 0:
        return a + multiply(a, b - 1)
    if b < 0:
        return -multiply(a, -b)

def multiply_unsigned(x, y):
    result = 0
    while y > 0:
        if y & 1:
            result += x
        x <<= 1
        y >>= 1
    return result

def count_set_bits(number):
    count = 0
    while number:
        count += number & 1
        number >>= 1
    return count

def bits_diff(a, b):
    count = 0
    diff = a ^ b
    while diff:
        count += diff & 1
        diff >>= 1
    return count

def bit_length(number):
    count = 0
    while number:
        count += 1
        number >>= 1
    return count

def is_power_of_two(number):
    return number != 0 and (number & (number - 1)) == 0

def full_adder(a, b):
    carry = 0
    result = 0
    i = 0
    while a != 0 or b != 0 or carry != 0:
        bit_a = a & 1
        bit_b = b & 1
        sum = bit_a ^ bit_b ^ carry
        result |= sum << i
        carry = (bit_a & bit_b) | (bit_a & carry) | (bit_b & carry)
        a >>= 1
        b >>= 1
        i += 1
    return result

fn get_bit(number: i32, bit_position: i32) -> i32 {
    (number >> bit_position) & 1
}

fn set_bit(number: i32, bit_position: i32) -> i32 {
    number | (1 << bit_position)
}

fn clear_bit(number: i32, bit_position: i32) -> i32 {
    number & !(1 << bit_position)
}

fn update_bit(number: i32, bit_position: i32, bit_value: i32) -> i32 {
    let mask = !(1 << bit_position);
    (number & mask) | (bit_value << bit_position)
}

fn is_even(number: i32) -> bool {
    (number & 1) == 0
}

fn is_positive(number: i32) -> bool {
    number >= 0 && (number & 0x80000000) == 0
}

fn multiply_by_two(number: i32) -> i32 {
    number << 1
}

fn divide_by_two(number: i32) -> i32 {
    number >> 1
}

fn switch_sign(number: i32) -> i32 {
    !number + 1
}

fn multiply(a: i32, b: i32) -> i32 {
    match b {
        0 => 0,
        _ if b > 0 => a + multiply(a, b - 1),
        _ => -multiply(a, -b),
    }
}

fn multiply_unsigned(x: i32, y: i32) -> i32 {
    let mut result = 0;
    let mut x = x;
    let mut y = y;
    while y > 0 {
        if y & 1 == 1 {
            result += x;
        }
        x <<= 1;
        y >>= 1;
    }
    result
}

fn count_set_bits(mut number: i32) -> i32 {
    let mut count = 0;
    while number != 0 {
        count += number & 1;
        number >>= 1;
    }
    count
}

fn bits_diff(a: i32, b: i32) -> i32 {
    let mut count = 0;
    let mut diff = a ^ b;
    while diff != 0 {
        count += diff & 1;
        diff >>= 1;
    }
    count
}

fn bit_length(mut number: i32) -> i32 {
    let mut count = 0;
    while number != 0 {
        count += 1;
        number >>= 1;
    }
    count
}

fn is_power_of_two(number: i32) -> bool {
    number != 0 && (number & (number - 1)) == 0
}

fn full_adder(a: i32, b: i32) -> i32 {
    let mut carry = 0;
    let mut result = 0;
    let mut i = 0;
    let mut a = a;
    let mut b = b;
    while a != 0 || b != 0 || carry != 0 {
        let bit_a = a & 1;
        let bit_b = b & 1;
        let sum = bit_a ^ bit_b ^ carry;
        result |= sum << i;
        carry = (bit_a & bit_b) | (bit_a & carry) | (bit_b & carry);
        a >>= 1;
        b >>= 1;
        i += 1;
    }
    result
}

function getBit(number: number, bitPosition: number): number {
  return (number >> bitPosition) & 1;
}

function setBit(number: number, bitPosition: number): number {
  return number | (1 << bitPosition);
}

function clearBit(number: number, bitPosition: number): number {
  return number & ~(1 << bitPosition);
}

function updateBit(
  number: number,
  bitPosition: number,
  bitValue: number,
): number {
  const mask = ~(1 << bitPosition);
  return (number & mask) | (bitValue << bitPosition);
}

function isEven(number: number): boolean {
  return (number & 1) === 0;
}

function isPositive(number: number): boolean {
  return number >= 0 && (number & 0x80000000) === 0;
}

function multiplyByTwo(number: number): number {
  return number << 1;
}

function divideByTwo(number: number): number {
  return number >> 1;
}

function switchSign(number: number): number {
  return ~number + 1;
}

function multiply(a: number, b: number): number {
  if (b === 0) {
    return 0;
  }
  if (b > 0) {
    return a + multiply(a, b - 1);
  }
  if (b < 0) {
    return -multiply(a, -b);
  }
  return 0;
}

function multiplyUnsigned(x: number, y: number): number {
  let result = 0;
  while (y > 0) {
    if (y & 1) {
      result += x;
    }
    x <<= 1;
    y >>= 1;
  }
  return result;
}

function countSetBits(number: number): number {
  let count = 0;
  while (number) {
    count += number & 1;
    number >>= 1;
  }
  return count;
}

function bitsDiff(a: number, b: number): number {
  let count = 0;
  let diff = a ^ b;
  while (diff) {
    count += diff & 1;
    diff >>= 1;
  }
  return count;
}

function bitLength(number: number): number {
  let count = 0;
  while (number) {
    count++;
    number >>= 1;
  }
  return count;
}

function isPowerOfTwo(number: number): boolean {
  return number !== 0 && (number & (number - 1)) === 0;
}

function fullAdder(a: number, b: number): number {
  let carry = 0;
  let result = 0;
  let i = 0;
  while (a !== 0 || b !== 0 || carry !== 0) {
    const bitA = a & 1;
    const bitB = b & 1;
    const sum = bitA ^ bitB ^ carry;
    result |= sum << i;
    carry = (bitA & bitB) | (bitA & carry) | (bitB & carry);
    a >>= 1;
    b >>= 1;
    i++;
  }
  return result;
}