Как эти два метода, чтобы найти, что сила числа 2, отличается?

Question

Итак, допустим, у меня есть число N, которое гарантированно будет иметь степень 2 и всегда больше 0. Теперь я написал два C метода, чтобы найти, на чем основана сила 2 N для побитовых операторов -

Метод A -

int whichPowerOf2(long long num) {
    int ret = -1;
    while (num) {
        num >>= 1;
        ret += 1;
    }

    return ret;
}

Метод B -

int whichPowerOf2(long long num) {
    int idx = 0;
    while (!(num & (1<<idx))) idx += 1;
    return idx;
}

Интуитивно оба метода кажутся одинаковыми и возвращают одинаковые значения для разных (меньших) значений N. Однако метод B не работает для меня, когда я пытаюсь представить свое решение проблемы кодирования.

Может кто-нибудь сказать мне, что здесь происходит? Почему метод А правильный и метод Б неправильный?

Answer 1

Проблема с этим подвыражением:

1<<idx

Константа 1 имеет тип int. Если idx становится больше, чем битовая ширина int, вы вызвали неопределенное поведение . Это указано в разделе 6.5.7p3 C стандарта относительно операторов побитового сдвига:

Целочисленные преобразования выполняются для каждого из операндов. Тип результата - тип повышенного левого операнда. Если значение правого операнда отрицательно или больше или равно ширине повышенного левого операнда, поведение не определено.

Измените константу на 1LL, чтобы дать ей тип long long, соответствующий типу num.

while (!(num & (1LL<<idx))) idx += 1;

Answer 2

В вашем методе B следующая строка может вызвать неопределенное поведение:

while (!(num & (1<<idx))) idx += 1;

Почему? Ну, выражение 1<<idx оценивается как int, потому что константа 1 является int. Кроме того, поскольку num - это long long (который, как мы предполагаем, имеет больше битов, чем int), то вы можете сместить влево больше, чем количество бит в int.

Чтобы исправить проблему, используйте суффикс LL на константе:

while (!(num & (1LL<<idx))) idx += 1;