Повернуть влево последние 10 бит в int

Мне нужно реализовать функцию, которая поворачивает влево последние 10 битов int.

Итак, если int имеет значение

0b 1111 0000 0000 0000 0000 1100 1100 0000

левое вращение на 2 дало бы нам

0b 1111 0000 0000 0000 0000 1111 0000 0000

Дальнейшее левое вращение на 1 дало бы

0b 1111 0000 0000 0000 0000 1110 0000 0001
  • ptr - указатель на данный int, который мы хотим повернуть
  • n - сколько раз мы хотим повернуть
void leftRotateLast10Digits(int * ptr, int n) {

}

Я понимаю, как это сделать, если мы хотим повернуть весь int, но я не уверен, как это сделать только для последних 10 цифр. Я думаю, что если повернуть int влево, это будет выглядеть примерно так, как показано ниже. Но все же я не понимаю, как повернуть только последние 10 цифр.

void leftRotate(int * ptr, int n) {
    int DROPPED_MSB;
    int INT_BITS = sizeof(int) * 8 - 1;
    int num = *ptr;

    // The effective rotation
    n %= INT_BITS;

    while(n) {
        DROPPED_MSB = (num >> INT_BITS) & 1; 

        // Left rotate num by 1 and set its dropped MSB as new LSB
        num = (num << 1) | DROPPED_MSB;
        n--;
    }
    *ptr = num;
}

c bitwise-operators byte-shifting
person scy17    schedule 09.07.2020    source источник
comment
Вы можете взять начальный номер и добавить к нему 0b1111111111111111111110000000000. Теперь у вас есть биты, которые не должны меняться. Вы можете сделать обратное и & начальное число с 0b1111111111. Эти 10 бит нужно вращать. Вы знаете, как это сделать. Наконец | оба числа вместе.   -  person Cheatah    schedule 09.07.2020
comment
1) значит в вращении задействованы только 10 младших битов, я правильно понял? 2) int INT_BITS = sizeof(int) * 8 - 1;, похоже, создает общую функцию, работающую для каждой архитектуры. Это требование? Будет ли приемлемо предположение о 4-байтовом целом?   -  person Roberto Caboni    schedule 09.07.2020
comment
scy17, вы хотите, чтобы эта ротация работала для n > 9, для n < 0?   -  person chux - Reinstate Monica    schedule 10.07.2020
comment
scy17 Примечание: int INT_BITS = sizeof(int) * 8 - 1; n %= INT_BITS; сомнительный код. Я ожидаю, что n %= INT_BITS + 1; и другие справятся с n < 0.   -  person chux - Reinstate Monica    schedule 10.07.2020

Ответы (2)


arrow_upward
4
arrow_downward

Я не уверен, как это сделать только для последних 10 цифр.

Изолируйте 10 бит от остальных.

Поверните 10 бит (я бы пропустил цикл while).

Или 10 бит обратно в int.

(Давайте использовать наименее, а не последний)

void leftRotateLeast10Digits(int *ptr, int n) {
  int value = *ptr;
  int ls10bits = value & 0x3FF;
  value ^= ls10bits;  // zero out the 10 LS bits.
  
  // If `n` outside [0...9] range needed
  n %= 10;
  if (n < 0) n += 10;

  // move LS bits left `n` times` and MS bits right `10-n` times.
  int rotated = (ls10bits << n) | (ls10bits >> (10-n));
  rotated &= 0x3FF;

  value |= rotated;
  *ptr = value;
}

Для поддержки 16-битного int потребовалась дополнительная работа. int ls10bits --> int_least32_t ls10bits, чтобы легко справиться с <<.
Я бы предположил, что это также работает для редкого дополнения, отличного от 2, когда результат не является ловушкой.

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

person chux - Reinstate Monica    schedule 09.07.2020

arrow_upward
0
arrow_downward

Относительно простой способ сделать это состоит в том, чтобы разделить целое число на две части: 10 битов, которые следует вращать, и другие (старшие) биты, которые не следует вращать. Затем, повернув соответствующую часть, восстановите остальные биты с помощью операции побитового ИЛИ:

void leftRotate(int* ptr, int n)
{
    int mask = 0x03FF; // Mask for lower 10 bits;
    int DROPPED_MSB;
    int INT_BITS = 10; // Only work with 10 bits
    int num = *ptr & mask; // Extract JUST low 10 bits
    int top = *ptr & ~mask; // Save all the OTHER bits
    n %= INT_BITS; // The effective rotation
    while (n) {
        DROPPED_MSB = (num >> INT_BITS) & 1;
        // Left rotate num by 1 and set its dropped MSB as new LSB
        num = (num << 1) | DROPPED_MSB;
        n--;
    }
    *ptr = num | top; // Restore the saved upper bits
}
person Adrian Mole    schedule 09.07.2020