Как проверить, установлен ли ровно один бит в целое число? - PullRequest
Новая
       100

Как проверить, установлен ли ровно один бит в целое число?

1 голос
/ 24 апреля 2020

Я хочу написать функцию HasOneBit, которая

  • принимает любой целочисленный тип (со знаком или без знака, от 8 до 64 бит),
  • равен constexpr,
  • не вызывает неопределенного поведения.

Я попытался обобщить это: 

bool HasOneBit (std::uint64_t value)
{
    return value != 0 && (value & (value - 1)) == 0;
}

Это приводит к потере значения, если тип value будет целым числом со знаком, и мы передали наименьшее значение функции. Должен ли я перегрузить функцию 8 раз, чтобы реализовать все возможности?

1 Ответ

1 голос
/ 24 апреля 2020

Следующая шаблонная функция удовлетворяет всем критериям ( live demo ): 

template <class T>
constexpr bool HasOneBit (T value)
{
    static_assert (std::is_integral<T>::value && !std::is_same<T, bool>::value,
                   "This function should be used only with integers.");

    const std::make_unsigned_t<T> unsignedValue = value;

    return unsignedValue != 0 && (unsignedValue & (unsignedValue - 1)) == 0;
}

Это не будет вызывать неопределенное поведение, потому что value сначала преобразуется в беззнаковый аналог T. Это преобразование не изменяет представление битов value.

Я думаю, что соответствующая цитата из стандарта такова (см. N4713 , [conv.integral] # 2):

Если тип назначения не имеет знака, полученное значение представляет собой целое число без знака, соответствующее целому числу источника (по модулю 2 n , где n - количество битов, используемых для представления типа без знака). [ Примечание: В представлении дополнения до двух это преобразование является концептуальным, и в битовой комбинации нет изменений (если нет усечения). - примечание конца ]

A более новая версия этого правила еще проще. Не уверен, относится ли это также к преобразованию без знака в знаковое.

В противном случае результатом является уникальное значение типа назначения, которое совпадает с целым числом источника по модулю 2 N , где N - ширина типа назначения.

...