Поверните 0 бит в 1 бит, если бит находится между низким и высоким

Question

Полное раскрытие информации, это проблема домашней работы, и мне не нужен точный код. Мне поручено воспроизвести следующий код, используя только ~ & + < <.

int result = 0; 
int i; 
for(i = lowbit; i <= highbit; i++) 
    result |= 1 << i; 
return result; 

Где lowbit и highbit являются параметрами между 0 и 31 включительно. Если lowbit это больше, чем число highbit, вернуть 0.

То, что я попытался так как для следующего код

int result = 0; 
int negone = ~0x0; 
int first = 1 << (lowbit + negone); //the first 1 bit is at the lowbit th location 
int last = 1 << (highbit + negone); //the last 1 bit is at the highbit th location 
int tick = ~(first + last); //attempting to get all bits in the range of low and highbit. 
result = ~(~first & ~tick); //bitwise | without using | 
result = ~(~last & ~result); 
return result + 1; //the first bit should always be on. 

Так есть что-то фундаментальное я здесь отсутствует? В дополнение к тому, что я не работаю, это также распространяется на мой лимит из 12 операторов, которые мне разрешено использовать, но я бы хотел попробовать и заставить его работать, прежде чем я даже начну ограничивать операторов.

Когда я запускаю тестовый сценарий, я получаю ошибки в большинстве тестов, в том числе lowbit и highbit равны друг другу. Случаи, где максимальный размер highbit и lowbit - это наименьший размер, похоже, работает.

Любая помощь будет высоко оценена.

Answer 1

negone должен быть инициализирован таким образом:

uint32_t negone = ~0UL; 

Вы добавляете номер бита с битов в:

int first = 1 << (lowbit + negone); //the first 1 bit is at the lowbit th location 
int last = 1 << (highbit + negone); 

Вы должны вместо этого вычислить 32 битовых масок

uint32_t first = negone << lowbit; // all bits below lowbit are 0, others are 1 
uint32_t last = negone << highbit << 1; // all bits above highbit are 1, other are 0 

Результат получается путем маскировки дополнения first с last:

uint32_t result = ~first & last; 

Сочетание вышеуказанных шагов дает прямое решение с 7 операторами (12 включая скобки и назначения), без добавления, и ни вычитания:

uint32_t result = ~(~0UL << highbit << 1) & (~0UL << lowbit); 

я использую 0UL потому что тип unsigned long имеет длину не менее 32 бит, тогда как тип unsigned int может иметь только 16 бит.

Answer 2

Исходный код генерирует блок 1 от lowbit до highbit (включительно). Это может быть достигнуто без петли следующим образом:

int nrOfBits = highbit + ~lowbit + 2; // highbit - lowbit + 1 
int shift = (nrOfBits & 0x1f + 1); 
int result = ~(~(1 << shift)+1) << lowbit; 

Идея заключается в том, что, например, диапазон 8 битов, заполненных с 1 означает количество 255, тогда как 2^8 является 256. Так что, поскольку оператор - не разрешен, мы используем 2-дополнение для получения -256, добавьте 1, чтобы получить -255, и верните его на +255 с использованием оператора с 2-мя дополнительными функциями ~. Затем нам просто нужно сдвинуть блок lowbits влево.

Answer 3

1) Создать маску с битами от низкого до высокого набора:

uint32_t mask = ~(~0ul << highbit << 1) & (~0ul << lowbit) 

Пример: lowbit = 4, highbit = 12 (9 бит)

mask = ~(0xffffffff << 12 << 1) & (0xffffffff << 4) 
    = ~(0xffff7000) & 0xfffffff0 
    = 0x00001fff & 0xfffffff0 
    = 0x00001ff0 

2) Применить маску значение, которое необходимо изменить, это просто операция |, но это недействительный оператор в этом упражнении, поэтому его необходимо преобразовать с помощью форума De Morgan:

A|B - >~(~A & ~B):

result = ~(~result & ~mask) ; 

Это, конечно, можно объединить два шага, но, возможно, ясность не будет затем служил.

Answer 4

Проблема может заключаться в том, что tick = ~(first+last) не переворачивает бит от младшего до высокого.

Может быть, мы можем сделать что-то вроде этого:

/* supposed that lowbit = 1, highbit = 2 */ 
uint32_t negone = ~(0u); /* negone = all 1s */ 
uint32_t first = negone << lowbit; /* first = ...111110 */ 
uint32_t last = (1 << (highbit + 1)) + negone; /* last = ...0000111 */ 
uint32_t tick = last & first; /* tick = ...000110 */ 
result = ~(~result&~tick); /* Bitwise Or without | as you mentioned. */ 

Это занимает 11 битовые операции, чтобы сделать это.

p.s. Мне интересно, почему первый бит должен быть всегда включен.

Редактировать: Чтобы избежать неопределенной операции, мы должны использовать неподписанный тип, например uint32_t.