Calcolo dell'alta potenza di 2 che divide uniformemente un numero in C

Ho bisogno di scrivere una logica per determinare, dato un numero pari. La più alta potenza di due che la divide in modo uniforme. Qual è il valore massimo di 2^n dove Input% 2^n == 0?Calcolo dell'alta potenza di 2 che divide uniformemente un numero in C

IE:
Input -> Output

4 (0100) -> 4 

8 (1000) -> 8 

12 (1100) -> 4 

14 (1110) -> 2 

24 (11000) -> 8 

etc....

sembra che ci sia una certa logica bit a bit che può funzionare out: quando si guarda l'ingresso in binario, il più a destra di un bit sembra essere una soluzione. Come posso determinare questo valore in C? C'è un'altra soluzione che potrebbe essere più semplice?

grazie- Jonathan

fonte

2009-10-11 Anonymous

Senza usare aritmetica in virgola mobile:

((x^(x - 1)) >> 1) + 1

casi semplificazione e laterali siano lasciati come esercizi per il lettore.

fonte

2009-10-11 21:15:59

X = 24 (24^23) = 24623 24623 >> 1 = 12311 12311 + 1 = 12312 Ti ho calcolare qualcosa che non va? –

Jonathan: '^' è XOR, quindi '(24^23)' è 15. – caf

BTW, se x non è firmato, credo che l'unico caso limite che richiede una gestione speciale sia zero. – caf

Se siete disposti ad assumere 2 complemento di aritmetica:

x & -x

Se si fanno un sacco di questo genere di cose (o anche se solo trovi interessante), ritrovi una copia del prenotare "Hacker's Delight".

modifica: avakar correttamente nota che questo non dipende dal complemento a 2 se il tipo non è firmato. La sezione del standard è §6.2.5, paragrafo 9:

Un calcolo coinvolge firmati operandi può mai troppopieno, perché un risultato che non può essere rappresentato da tipo intero senza segno risultante è ridotta modulo il numero che è uno superiore al valore più grande che può essere rappresentato dal tipo risultante.

"uno maggiore del valore più grande" lascia qualche scappatoia per un'implementazione particolarmente perversa (in particolare, un'implementazione che non fa uso di binario, per esempio), ma sei abbastanza improbabile incontrare questo.

fonte

2009-10-11 21:23:23

molto conciso, mi piace! –

+1. Per la cronaca, non devi assumere il complemento a 2. Questo funzionerà facilmente su qualsiasi architettura, a condizione che 'x' sia di tipo aritmetico senza segno. – avakar

Supponiamo di avere un tipo a 32 bit con aritmetica del complemento a 1: se x è 1, quindi '-x' è' 0xfffffffe', e 'x & -x' è 0, che non è la risposta che l'interrogante vuole. Come nota J.F. Sebastian, * puoi * aggirare questo problema usando 'x & (~ x + 1)', che è la negazione del complimento di solo 2 espansa in due operazioni. –

Possiamo sostituire (-x) da (~x + 1):

x & (~x+1)

Low Level Bit Hacks You Absolutely Must Know fornisce una spiegazione dettagliata.

fonte

2009-10-11 21:57:51 jfs

Nota che (~ x + 1) è la definizione di -x nel complemento a 2. Ciò rende questa risposta leggermente migliore di x & (-x), dato che (~ x + 1) dipende solo dalla macchina che utilizza l'aritmetica binario lineare, che è praticamente un dato di questi tempi (ma non sempre!). –

Un numero nella forma 2^n è scritto in binario da un 1 seguito da una serie di 0 o più 0. Ad esempio, 1, 10, 100, 1000, ecc ... sono tutti potenza di 2.

Per ottenere la massima potenza di 2 che divide un dato numero, si possono fare le seguenti due fasi:

Scrivere il numero in formato binario. Ad esempio, se il numero è 168, scrivere 10101000.
esercizio fuori tutti i bit prima che il primo bit da destra che contiene 1. Nel caso di 168, ciò che rimane è 1000 (= 8 in decimale) dopo colpisce fuori prima parte 10101000.

Ciò che rimane è il risultato, ovvero la massima potenza di 2 che divide il numero.

A livello di programmazione, x è il tuo numero di input. Poi l'output desiderato sarà: x - (x^(x-1))

Spiegazione:

x^(x-1) [cioè x XOR x-1] si libera del primo 1 da LSB (bit meno significativo) lato

x - (x^(x-1)) si libera del parte rimanente e conserva solo il primo 1 dal lato LSB.

fonte

2012-12-27 08:04:38

Calcolo dell'alta potenza di 2 che divide uniformemente un numero in C

risposta

Problemi correlati