Bitshifts per ottenere il resto

Voglio sapere come ottenere il resto dividendo un numero intero con un altro intero (entrambi positivi) utilizzando solo operatori bitshift o bitwise. L'operatore / o l'operatore % non devono essere utilizzati.Bitshifts per ottenere il resto

Ad esempio, per ottenere il resto quando il divisore ha il formato 2^k, la seguente operazione restituisce il resto.

m = Remainder

n = The number

d = The divisor

m = n & (d - 1)

Tuttavia questo metodo funziona solo quando è d della forma 2^k. Voglio conoscere un metodo simile per i non-poteri di 2. Attualmente sto lavorando su un problema da programming challenges e voglio utilizzare tale metodo per ridurre i tempi di esecuzione del programma

fonte

2012-11-25 Extreme Coders

Non il fatto che la rappresentazione di bit sia solo in base-2 sia una limitazione? Considera il valore 43/7 - il valore è in realtà 6.142857 .... Quale approccio generico hai considerato per un valore in una base superiore a 2? – Makoto

Non esiste un metodo generale. È possibile sostituire la divisione con una moltiplicazione e alcuni spostamenti e addizioni/sottrazioni se si conosce il divisore, però. Chiedilo a qualsiasi compositore C competente e ti darà i valori magici per ogni costante di tempo di compilazione. –

A meno che la risposta non contenga solo una dichiarazione di 1 bit, scommetto che non si batta l'operatore mod javas. – goat

Qualsiasi risposta che non utilizza l'operatore % sarà una risposta meno efficiente, ma, se proprio non è possibile utilizzare la operatore, quindi, una soluzione è quella di utilizzare un ciclo per sottrarre d da n ripetutamente:

m = n; 
while (m >= d) 
{ 
    m -= d; 
}

Supponendo che i numeri interi sono a 32-bit, allora si può considerare una versione ottimizzata in cui cancelliamo multipli di d da n:

m = n; 
for (i = 31; i >= 0; i--) 
{ 
    di = d << i; 
    if (di > 0 && m >= di) m -= di; 
}

In questo esempio, si presume che gli interi siano firmati e gli orologi per l'overflow, ovvero il test per di > 0.

fonte

2012-11-25 23:08:29

sfortunatamente, un turno di overflow non porta necessariamente a un numero negativo, anche se si presuppone una normale macchina a 2 secondi. –

risposta

Problemi correlati