Задачи

Разбираем битовую задачку

Разбираем битовую задачку

Сегодня в ежедневной задаче на литкоде попалась интересная штука — нужно найти наименьшее число, которое не меньше заданного N и состоит только из единиц в двоичной записи.

Вам дают число, например, 10 (в двоичной системе это 1010). Нужно найти ближайшее число >= 10, где все биты — единицы. В данном случае это 15 (двоичная 1111).

Первое решение, которое приходит в голову. Можно просто пройтись по всем битам исходного числа и установить каждый в 1:

func smallestNumber(n int) int {
    result := 0
    bitPosition := 0
    
    for n > 0 {
        result |= (1 << bitPosition)  // устанавливаем бит
        bitPosition++
        n >>= 1  // сдвигаем к следующему биту
    }
    
    return result
}

Работает, но есть способ элегантнее. Решение в одну строчку:

Вспомните, как выглядят числа-степени двойки минус один:

2¹ - 1 = 1 (двоичная: 1)
2² - 1 = 3 (двоичная: 11)
2³ - 1 = 7 (двоичная: 111)
2⁴ - 1 = 15 (двоичная: 1111)

Видите паттерн? Нам нужно найти самый старший бит в исходном числе и взять следующую степень двойки минус один.

Для числа 10 (двоичная 1010) старший бит на позиции 3. Значит, берём 2⁴ - 1 = 15.

func smallestNumber(n int) int {
    x := 1
    for x - 1 < n {
        x <<= 1  // умножаем на 2
    }
    return x - 1
}

Или через битовые операции с помощью bits.Len:

import "math/bits"

func smallestNumber(n int) int {
    bitLength := bits.Len(uint(n))  // находим количество бит
    return (1 << bitLength) - 1
}

Число с N единицами подряд — это всегда 2^N - 1. Мы находим, сколько битов нужно, чтобы вместить наше число, и берём число с таким количеством единиц.