Leetcode Tag Search | Back

Bit manipulation

Category: /template

Template

Explaination Details Template Index
def find_rightmost_1(number):
    if not number: return 0
    rightmost_set_bit = 1
    while (rightmost_set_bit & number) == 0:
        rightmost_set_bit = rightmost_set_bit << 1
    return rightmost_set_bit

def find_rightmost_0(number):
    if not number: return 0
    cnt = 0
    while (number & 1) == 1:
        number >>= 1
        cnt += 1
    return cnt  # or return 1 << cnt

    # result for reference
    (0, 0), (1, 1), (2, 0), (3, 2), (4, 0),
    (5, 1), (6, 0), (7, 3), (8, 0), (9, 1),

This can be used as a trick to separate numbers into two groups based this bit. E.g.

    num1, num2 = 0, 0

    for num in nums:
        if (num & rightmost_set_bit) != 0:  # the bit is set
            num1 ^= num
        else:  # the bit is not set
            num2 ^= num

Bitwise to find the missing number

讨论

提示

  • 如果看不到讨论部分, 请暂时关掉adblock in Firefox/Chrome
  • 本网站使用Javascript实现评论功能, 此处外链对提高您的网站PR没有帮助. (潜台词: 请不要灌水, 谢谢)