thoughtbook

Saturday, March 4, 2023

Bitwise and of numbers range

Leetcode 201 problem.

Go

Using bit

Time complexity: $O(n)$ - n is a quantity of numbers between 2 given numbers
Auxiliary space: $O(1)$ - constant amount of space

func rangeBitwiseAnd(left int, right int) int {
    difference := right - left
    bit := uint(0)

    // counting how many bits to move
    for difference != 0 {
        difference = difference >> 1
        bit++
    }
    
    // shift and AND both left and right
    return (left >> bit << bit) & (right >> bit << bit)
}

Iteration AND

Time complexity: $O(n)$ - n is a quantity of numbers between 2 given numbers
Auxiliary space: $O(1)$ - constant amount of space

func rangeBitwiseAnd(left int, right int) int {
    for right > left && right != 0 {
        // AND every consecutive number
        right = right & (right - 1)
    }
    
    return right
}

Counting solution

Time complexity: $O(log(n))$ - n is a quantity of numbers between 2 given numbers
Auxiliary space: $O(1)$ - constant amount of space

func rangeBitwiseAnd(left int, right int) int {
    // shift until common prefix
    shifts := 0
    for left != right {
        left = left >> 1
        right = right >> 1 
        shifts++
    }
    
    // shift back to get the prefix in original bit positions
    return left << shifts
}