Интервью - бит операции

Question

Меня попросили реализовать invert(x,p,n), который возвращает x с n битами, которые начинаются с позиции p инвертированной (т. Е. 1 изменено на 0 и наоборот), оставляя остальные неизменными.

Мое решение:

unsigned invert(unsigned x, int p, int n) 
{ 
     return (x^(((1 << (n + 1)) - 1) << (p - n + 1))); 
} 

я нашел на сети это решение проблемы:

unsigned invert(unsigned x, int p, int n) 
{ 
    return x^((~(~0<<n))<< p+1-n); 
} 

Для меня это выглядит неправильно - Что такое правильный и эффективный подход к проблеме

Answer 1

Ну, ваша реализация явно неверна; Рассмотрим p = 1, n = 2:

x^(((1 << (n + 1)) - 1) << (p - n + 1)) 
x^(((1 << 3) - 1) << 0) 
x^((8 - 1) << 0) 
x^7 

Это переворачивает три бита низкого порядка х, а не два. Мы можем исправить это, используя вместо этого:

return x^(1 << n) - 1 << p - n + 1; 

(Я также избавился от обильных ложных круглых скобок). У этого все еще есть ошибка в углу; если вызывающий абонент хочет перевернуть все, кроме одного бита (то есть n == sizeof x * CHAR_BIT - 1). Предположим, что ИНТ 32 бит и работать пример:

x^(1 << n) - 1 << p - n + 1; 
x^(1 << 31) - 1 << p - 31 + 1; 
    ^^^^^^^^^ 
    ruh-roh! 

К сожалению, это вызывает неопределенное поведение (С11, §6.5.7 пункт 4):

Если E1 имеет подписанный тип и неотрицательным значение и E1 × 2 ^E2 представляется в виде результата, то это результирующее значение; в противном случае поведение не определено.

Вы можете исправить это путем постоянного 1 знака ...

return x^(1U << n) - 1 << p - n + 1; 

... но тогда вы еще имеют неопределенные поведение при n == sizeof x * CHAR_BIT (то есть, если абонент хочет перевернуть все биты) (С11, §6.5.7 пункт 3):

Если значение о f правый операнд ... больше или равен ширине продвинутого левого операнда, поведение не определено.

Решение, которое вы нашли в сети, также имеет неопределенное поведение таким же образом. Если вы действительно хотите, чтобы получить все крайние случаи маниакально педантично правильно, вам нужно сделать что-то вдоль этих линий:

unsigned invert(unsigned x, int p, int n) { 
    if (p < 0 || p >= sizeof x * CHAR_BIT) { 
     /* flip out and kill people */ 
    } 
    if (n < 0 || n > p + 1) { 
     /* (╯°□°）╯︵ ┻━┻) */ 
    } 
    if (n == sizeof x * CHAR_BIT) return ~x; 
    /* Having dealt with all the undefined cases, 
     we can safely use your nice expression. 
     But without all the parentheses. Superfluous 
     parentheses make hulk angry. */ 
    return x^(1U << n) - 1 << p - n + 1; 
} 

Является ли это педантичный излишеством? Да. Буду ли я ожидать, что кто-то напишет это в качестве первого прохода в ситуации с интервью? Нет. Хотел бы я, чтобы они могли разумно обсудить связанные с этим опасности? Да.