Spostamento a sinistra di propagazione LSB, equivalente concettuale del passaggio a destra di propagazione del segno [chiuso]

Beh, se non mi interessasse la performance (e non lo faccio mai prima di doverlo fare) lo farei nel modo più semplice a cui possa pensare.

Presunzione di una lingua (come c) in cui ho il spostamento corretto aritmetico (quello che chiami spostamento a destra di propagazione del segnale), e presumendo che so come inverte i bit in un registro quindi posso creare il tuo" equivalente a sinistra "in questo modo:

• reverse bit
• aritmetica destra spostamento x bit

• bit di inversione
  

  1 <<< 7: "11111111" 
  
  00000001 <- 1
  10000000 <- reverse   
  11111111 <- arithmetic right shift (7) 
  11111111 <- reverse
  
  0 <<< 7: "00000000"
  00000000 <- 0
  00000000 <- reverse   
  00000000 <- arithmetic right shift (7)
  00000000 <- reverse   
  
  15 <<< 3: "01111111"
  00001111 <- 15
  11110000 <- reverse   
  11111110 <- arithmetic right shift (3)
  01111111 <- reverse   
  

Questo è probabilmente lento ma utilizza un codice ben testato ed è concettualmente semplice. Quindi almeno può essere la base per i test contro i metodi più veloci.

Questa prossima idea non è stata testata, ma in cima alla mia testa un percorso più diretto sarebbe spostarsi a sinistra, mascherare il bit che è necessario propagare, sottrarre 1 e or con il risultato del turno.

    15 <<< 3 :"01111111"
    00001111 <- 15
    01111000 <- left shift 
    00001000 <- mask out propagating bit.  If result is zero, return the shift
    00000111 <- subtract 1
    01111111 <- OR with result of shift (01111000)

Non mi fiderei di questo finché non l'avrò testato. Ma questo sembra funzionare:

    result = ((n&1)==1)?(n<<x|(1<<x)-1):(n<<x);

Fatto senza diramazione, un altro performant versione, suggerita da @ErikEidt, sarebbe:

    y = (n & 1); 
    result = ((n << x) | ((y << x) - y));

Fatto in questo modo lo spostamento ( n<<x ) è OR 'ed con zero quando non si propagano quindi non c'è bisogno di diramazioni.

Cattura il bit basso prima del turno. Quindi spostare a sinistra della quantità desiderata. Ora prova il bit basso catturato. Se il bit basso era 0 , non rimane nulla da fare. Se era 1 , e hai cambiato, diciamo, 5 , allora puoi OR nel risultato spostato il valore: (1<<5)-1 , che sarà 5 un bit nella posizione più bassa. Se hai una quantità variabile in una variabile, sostituiscila con la 5.