Вопрос по c – Побитовое вращение левой функции

8

Я пытаюсь реализовать функцию поворота влево, которая вращает целое число х влево на п бит

Ex: rotateLeft(0x87654321,4) = 0x76543218 Legal ops: ~ & ^ | + << >>

пока у меня есть это:

<code>int rotateLeft(int x, int n) {
  return ((x << n) | (x >> (32 - n)));
}
</code>

который я понял, чтобы не работать для целых чисел со знаком .. Есть ли у кого-нибудь идеи, как это исправить?

так что теперь я попробовал:

<code>int rotateLeft(int x, int n) {
  return ((x << n) | ((x >> (32 + (~n + 1))) & 0x0f));
}
</code>

и получите ошибку:

ОШИБКА: сбой теста rotateLeft (-2147483648 [0x80000000], 1 [0x1]) ... ... дает 15 [0xf]. Должно быть 1 [0x1]

Вы можете создать маску для & amp; посторонний 1 бит? George Skoptsov
Хорошо, так что я думаю, что я выяснил, как избавиться от - путем (32 + (~ n + 1)), но у меня возникают проблемы с выяснением, что я могу сделать после | чтобы сделать эту работу asdfghjkl
@shaynie Пройдите этот урок, чтобы понять побитовые операторы:cprogramming.com/tutorial/bitwise_operators.html Тогда эта проблема будет намного проще. George Skoptsov
да, но у меня нет c знаний до этого, поэтому я не знаком с побитовыми операторами и не знаю, как использовать маску asdfghjkl
Подумайте, почему ваше выражение не работает для целых чисел со знаком и что вы можете сделать для части справа от оператора or, чтобы заставить его работать. Также обратите внимание, что- не входит в ваш список законных операторов, поэтому вам также необходимо это исправить. George Skoptsov

Ваш Ответ

5   ответов
0

является ли это вашим языком реализации или нет, но он наверняка выглядит так), сдвиг вправо на целое число со знаком, отрицательное значение которого определяется реализацией и поэтому его следует избегать.

Если вы все равно делаете битопы, выreally сначала следует привести к целому числу без знака.

0
int rotateLeft(int x, int n) {
  return (x << n) | (x >> (32 - n)) & ~((-1 >> n) << n);
}

int rotateLeft(int x, int n) {
  return (x << n) | (x >> (32 - n)) & ~(-1 << n);
}

не использовать "-" версия.

int rotateLeft(int x, int n) {
    return (x << n) | (x >> (0x1F & (32 + ~n + 1))) & ~(0xFFFFFFFF << n);
}

//test program
int main(void){
    printf("%x\n",rotateLeft(0x87654321,4));
    printf("%x\n",rotateLeft(0x87654321,8));
    printf("%x\n",rotateLeft(0x80000000,1));
    printf("%x\n",rotateLeft(0x78123456,4));
    printf("%x\n",rotateLeft(0xFFFFFFFF,4));
    return 0;
}
/* result : GCC 4.4.3 and Microsoft(R) 32-bit C 16.00.40219.01
76543218
65432187
1
81234567
ffffffff
*/
Это непереносимо, т. Е. Предполагает наличие совместимого с Intel чипа внутри.
Я не уверен, что вы спрашиваете. Она не знает, что такое маска и как она работает, поэтому ей нужно сначала изучить ее. В любом случае, в вашем ответе(-1 >> n) не имеет никакого эффекта - понимаете почему? Лучше просто использовать ~ 0.
Кроме того, это предотвращает оптимизацию счетчика времени компиляции вrol eax, imm8или от полной оптимизации, если значение также является константой после встраивания.
Заставление компилятора сохранять / перезагружать значение и счет - это огромные накладные расходы и намного хуже, чем то, что вы получаете от C, которое компилятор распознает и превращает обратно вrol инструкция.MSVC-style inline asm is terrible for wrapping single instructions.
12

это сообщество-вики Q & A, Код из Википедии не дает очень хороший asm с clang или gcc старше 5.1.

Там очень хорошее, подробное объяснение вращения бита, например кругового сдвигаВикипедия.

Цитирую оттуда:

unsigned int _rotl(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
      return value;
    return (value << shift) | (value >> (sizeof(value)*8 - shift));
}

unsigned int _rotr(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
      return value;
    return (value >> shift) | (value << (sizeof(value)*8 - shift));

В вашем случае, поскольку у вас нет доступа к оператору умножения, вы можете заменить*8 с<< 3.

EDIT Вы также можете удалитьif заявления с учетом вашего заявления, что вы не можете использоватьif, Это оптимизация, но вы все равно получите правильное значение без нее.

Обратите внимание, что если вы действительно собираетесь вращать биты наsigned целое число, интерпретация повернутого результата будет зависеть от платформы. В частности, это будет зависеть от того, использует ли платформаДва дополнения или жеОдно дополнение, Я не могу думать о приложении, в котором имеет смысл вращать биты целого числа со знаком.

В этом случае вы можете просто сделать математику и заменитьsizeof(value)*8-1 с4*8-1 = 31 а такжеsizeof(value)*8 с32.
я понимаю, что такое битовое вращение и как оно работает, но я должен запрограммировать его только с помощью побитовых операций, перечисленных выше asdfghjkl
Как примечание стороны; Я бы заменил8 сCHAR_BIT отlimits.h.
Есть ли в перечисленной реализации что-то, к чему у вас нет доступа? Обратите внимание, что вы можете заменить- 1 с+ -1 а также*8 с<<3.
Я не имею права использовать sizeOf или вызывать какие-либо другие функции, и для справки, мы должны предположить, что наши 32-битные целые числа используют два дополнения asdfghjkl
0

signed int?

Я бы просто бросилx дляunsigned int и выполните вращение, как у вас есть прямо сейчас.

На другом замечании: ваш код должен работать на разных архитектурах (не только 32-битных)? Вы можете избежать жесткого кодированияint bitsize.

я не могу использовать любой тип приведения, и мы должны предположить, что целое число составляет 32 бита asdfghjkl
Вы понимаете, почему ваше выражение не работает для целых чисел со знаком?
так как бы вы избавились от лишних 1с?
да, потому что & gt; & gt; заполняется 1 с, тогда как & lt; & lt; заполняется 0s asdfghjkl
0

int rotateLeft(int x, int n)
{
    _asm
    {
        mov eax, dword ptr [x]
        mov ecx, dword ptr [n]
        rol eax, cl
    }
}

Если вам нужно повернутьint переменнаяright in your code, затемthe fastest way is:

#define rotl( val, shift ) _asm mov eax, dword ptr[val] _asm mov ecx, dword ptr [shift] _asm rol eax, cl _asm mov dword ptr [val], eax

val это значение, которое вы вращаете,shift это длина вращения.

Кроме того, это предотвращает оптимизацию счетчика времени компиляции вrol eax, imm8или от полной оптимизации, если значение также является константой после встраивания.
Заставление компилятора сохранять / перезагружать значение и счет - это огромные накладные расходы и намного хуже, чем то, что вы получаете от C, которое компилятор распознает и превращает обратно вrol инструкция.MSVC-style inline asm is terrible for wrapping single instructions.
Это непереносимо, т. Е. Предполагает наличие совместимого с Intel чипа внутри.

Похожие вопросы