Bitwise ruotare funzione

Question

Sto cercando di implementare una funzione di rotazione che ruota sinistra un intero x data da n bit

lasciato

• Es: rotateLeft (0x87654321,4) = 0x76543218
• ops legali: ~ &^| + < < >>

Finora ho questo:

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

che ho capito di non lavorare per integers..does firmato Qualcuno ha qualche idea su come risolvere questo problema?

così ora ho provato:

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

e riceve l'errore:

ERRORE: test rotateLeft (-2147483648 [0x80000000], 1 [0x1]) non è riuscito ... ... Dà 15 [0xf]. Dovrebbe essere 1 [0x1]

Answer 1

Puoi definire 'ruota sinistra' per un signed int?

Vorrei semplicemente trasmettere x a un unsigned int ed eseguire la rotazione nel modo in cui lo avete ora.

In un'altra nota: il codice deve funzionare su architetture diverse (non solo a 32 bit)? Si consiglia di evitare di codificare il bit int.

Answer 2

Le migliori pratiche attuali per i rotatori compatibili con i compilatori sono this community-wiki Q&A. Il codice di wikipedia non produce molto bene con clang, o gcc più vecchio di 5.1.

C'è una spiegazione molto buona e dettagliata della rotazione dei bit a.k.a. shift circolare su Wikipedia.

Citando da lì:

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)); 

Nel tuo caso, dal momento che non ha accesso a l'operatore di moltiplicazione, è possibile sostituire con *8<< 3.

EDIT È inoltre possibile rimuovere le if dichiarazioni rese la sua dichiarazione che non è possibile utilizzare if. Questa è un'ottimizzazione, ma ottieni comunque il valore corretto senza di essa.

Si noti che, se si intende veramente ruotare i bit su un numero intero signed, l'interpretazione del risultato ruotato dipenderà dalla piattaforma. In particolare, dipenderà dal fatto che la piattaforma utilizzi Two's Complement o One's Complement. Non riesco a pensare a un'applicazione in cui è significativo ruotare i bit di un intero con segno.

Answer 3

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

UPDATE: (grazie mille @George)

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

Non utilizzare '-' versione.

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 
*/ 

Answer 4

In ISO C (idea se questo è il vostro linguaggio di implementazione o no, ma sembra sicuro di simile), spostare a destra su un numero intero con segno che è negativo è la realizzazione definiti e dovrebbero quindi essere evitati.

Se stai facendo bitops comunque, lo in realtà deve essere eseguito prima per interi senza segno.

Answer 5

Il modo migliore è:

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

Se avete bisogno di ruotare un variabile int destra nel codice, quindi il modo più veloce è:

#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 è il valore si ruota, shift è la lunghezza della rotazione.