Cálculo de la potencia máxima de 2 que divide uniformemente un número en C

Necesito escribir algo de lógica para determinar, dado un número par. El poder más alto de dos que lo divide equitativamente. ¿Cuál es el valor máximo de 2^n donde Entrada% 2^n == 0?Cálculo de la potencia máxima de 2 que divide uniformemente un número en C

IE:
de entrada -> Salida

4 (0100) -> 4 

8 (1000) -> 8 

12 (1100) -> 4 

14 (1110) -> 2 

24 (11000) -> 8 

etc....

parece que haya alguna lógica bit a bit que pueden funcionar: cuando se mira en la entrada en el sistema binario, el bit de la derecha parece ser la solución. ¿Cómo determino este valor en C? ¿Hay alguna otra solución que pueda ser más fácil?

de Acción de Gracias Jonathan

Fuente

2009-10-11 Anonymous

Sin utilizar la aritmética de punto flotante:

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

casos de simplificación y de borde se dejan como ejercicios para el lector.

Fuente

2009-10-11 21:15:59

X = 24 (24^23) = 24623 24623 >> 1 = 12311 12311 + 1 = 12312 ¿He calcular algo mal? –

Jonathan: '^' es XOR, de modo '(24^23)' es 15. – caf

Por cierto, si x es unsigned entonces creo que el único caso de borde que necesita un manejo especial es cero. – caf

Si usted está dispuesto a asumir de 2 aritmética de complemento:

x & -x

Si usted hace una gran cantidad de este tipo de cosas (o incluso si sólo parece interesante), se encuentra un ejemplar de la libro "Hacker's Delight".

editar: avakar correctamente nota que esto no depende del complemento 2 si el tipo no está firmado. La sección pertinente de la norma es §6.2.5, párrafo 9:

Un cálculo que implica sin signo operandos nunca puede desbordamiento, porque un resultado que no puede ser representado por el tipo entero sin signo resultante es reducido módulo el número que es uno mayor que el valor más grande que se puede representar con el tipo resultante .

"uno mayor que el valor más grande" deja un margen de maniobra para una aplicación especialmente perverso (en particular, una aplicación que no utiliza binario, por ejemplo), pero que está bastante poco probable que encuentre que.

Fuente

2009-10-11 21:23:23

muy conciso, me gusta! –

+1. Para el registro, no tienes que asumir el complemento de 2. Esto funcionará de forma portátil en cualquier arquitectura, siempre que 'x' sea de tipo aritmético sin signo. – avakar

Digamos que tenemos un tipo de 32 bits con la aritmética de complemento a 1: si x es 1, entonces '' -x' es 0xfffffffe', y 'X & -x' es 0, lo que no es la respuesta del interlocutor desea. Como observa J.F. Sebastian, usted * puede * evitar esto usando 'x & (~ x + 1)', que es solo una negación complementaria de 2 expandida en dos operaciones. –

Podemos reemplazar (-x) por (~x + 1):

x & (~x+1)

Low Level Bit Hacks You Absolutely Must Know proporciona una explicación detallada.

Fuente

2009-10-11 21:57:51 jfs

Tenga en cuenta que (~ x + 1) es la definición de -x en complemento a 2. Eso hace que esta sea una respuesta ligeramente mejor que x & (-x), ya que (~ x + 1) solo depende de la máquina que use aritmética binaria directa, que es casi un hecho en estos días (¡pero no siempre!). –

Un número en la forma 2^n está escrito en binario por un 1 seguido de una serie de 0 o más 0s. Por ejemplo, 1, 10, 100, 1000, ... etc, todos ellos potencia de 2.

Para conseguir la mayor potencia de 2 que divide un número dado, puede hacer los dos pasos siguientes:

Escriba el número en forma binaria. Por ejemplo, si el número es 168, escriba 10101000.
Huelga de todos los bits antes de que el primer bit de lado derecho que contiene 1. En el caso de 168, lo que queda es 1000 (= 8 en decimal) después de golpear off primera parte de 10101000.

lo que queda es el resultado - es decir, la más alta potencia de 2 que divide el número.

mediante programación, sea x es el número de la entrada. Entonces su salida deseada será: x - (x^(x-1))

Explicación:

x^(x-1) [es decir, x XOR x-1] se deshace de la primera 1 de lado LSB (bit menos significativo)

x - (x^(x-1)) se deshace de la parte restante, y conserva solo el primer 1 del lado LSB.

Fuente

2012-12-27 08:04:38

Cálculo de la potencia máxima de 2 que divide uniformemente un número en C

Respuesta

Cuestiones relacionadas