c++ - programa - Imprima el número de 1s en una secuencia hasta un número, sin contar realmente 1s

programa para adivinar un numero en c++

Question

Una pregunta de entrevista:

Haga un programa que tome la entrada ''N'' (sin signo largo) e imprima dos columnas, la primera columna imprime números del 1 al N (en formato hexadecimal) y la segunda columna imprime el número de 1s en la representación binaria del número en la columna izquierda . La condición es que este programa no debe contar 1s (por lo que no hay cálculos ''por número'' para obtener 1s / sin operadores de división).

Intenté implementar esto aprovechando el hecho de que No de 1s en 0x0 a 0xF se puede reutilizar para generar 1s para cualquier número. Estoy pegando código (uno básico sin comprobación de errores). Da resultados correctos, pero no estoy contento con el uso del espacio. ¿Cómo puedo mejorar esto? (Tampoco estoy seguro de si es lo que buscaba el entrevistador).

void printRangeFasterWay(){
uint64_t num = ~0x0 ;
cout << " Enter upper number " ;
cin >> num ;
uint8_t arrayCount[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4} ;
// This array will store information needed to print
uint8_t * newCount = new uint8_t[num] ;
uint64_t mask = 0x0 ;
memcpy(newCount, &arrayCount[0], 0x10) ;
uint64_t lower = 0;
uint64_t upper = 0xF;
uint64_t count = 0 ;
uint32_t zcount= 0 ;
do{
upper = std::min(upper, num) ;
for(count = lower ; count <= upper ; count++){
newCount[count] = (uint32_t)( newCount[count & mask] + newCount[(count & ~mask)>>(4*zcount)]) ;
}
lower += count ;
upper |= (upper<<4) ;
mask = ((mask<<4) | 0xF ) ;
zcount++ ;
}while(count<=num) ;
for(uint64_t xcount=0 ; xcount <= num ; xcount++){
cout << std::hex << " num = " << xcount << std::dec << " number of 1s = " << (uint32_t)newCount[xcount] << endl;
}
}

Editado para agregar muestra de ejecución

Enter upper number 18
num = 0 number of 1s = 0
num = 1 number of 1s = 1
num = 2 number of 1s = 1
num = 3 number of 1s = 2
num = 4 number of 1s = 1
num = 5 number of 1s = 2
num = 6 number of 1s = 2
num = 7 number of 1s = 3
num = 8 number of 1s = 1
num = 9 number of 1s = 2
num = a number of 1s = 2
num = b number of 1s = 3
num = c number of 1s = 2
num = d number of 1s = 3
num = e number of 1s = 3
num = f number of 1s = 4
num = 10 number of 1s = 1
num = 11 number of 1s = 2
num = 12 number of 1s = 2

Answer 1

Explicación

El siguiente algoritmo es como el suyo, pero amplía la idea (si entendí su enfoque correctamente). No realiza ningún cálculo ''por número'' como lo indica la pregunta, sino que utiliza una recursión que existe entre secuencias de longitudes que son potencias de 2. Básicamente, la observación es que para la secuencia 0, 1,..,2^n-1 , podemos usar la secuencia 0, 1, ...,2^(n-1)-1 en el siguiente manera.

Sea f(i) el número de unos en el número i luego f(2^(n-1)+i)=f(i)+1 para todos 0<=i<2^(n-1) . (Verifica esto por ti mismo)

Algoritmo en C ++

#include <stdio.h>
#include <stdlib.h>
int main( int argc, char *argv[] )
{
const int N = 32;
int* arr = new int[N];
arr[0]=0;
arr[1]=1;
for ( int i = 1; i < 15; i++ )
{
int pow2 = 1 << i;
int offset = pow2;
for ( int k = 0; k < pow2; k++ )
{
if ( offset+k >= N )
goto leave;
arr[offset+k]=arr[k]+1;
}
}
leave:
for ( int i = 0; i < N; i++ )
{
printf( "0x%8x %16d", i, arr[i] );
}
delete[] arr;
return EXIT_SUCCESS;
}

Tenga en cuenta que en el bucle for

 for ( int i = 0; i < 15; i++ )

puede haber desbordamiento en números negativos si supera los 15, de lo contrario, utilice int sin signo si desea ir más alto.

Eficiencia

Este algoritmo se ejecuta en O(N) y utiliza el espacio O(N) .

Answer 2

Aquí hay un enfoque que tiene complejidad de tiempo O (nlogn) y uso de memoria O (1). La idea es obtener el equivalente hexadecimal del número e iterar sobre él para obtener el número de unidades por dígito hexadecimal.

int oneCount[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
int getOneCount(int n)
{
char inStr[70];
sprintf(inStr,"%X",n);
int i;
int sum=0;
for(i=0; inStr[i];i++)
{
if ( inStr[i] > ''9'' )
sum += oneCount[inStr[i]-''A'' + 10];
else
sum+= oneCount[inStr[i] -''0''];
}
return sum;
}
int i,upperLimit;
cin>>upperLimit;
for(i=0;i<=upperLimit;i++)
{
cout << std::hex << " num = " << i << std::dec << " number of 1s = " << getOneCount(i) << endl;
}

Answer 3

Se puede hacer de forma relativamente trivial en tiempo constante con la conmutación de bits apropiada. Sin contar 1s y sin divisiones. Creo que estaba en el camino correcto al mantener la matriz de valores de bits conocidos:

int bits(int x)
{
// known bit values for 0-15
static int bc[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
// bit "counter"
int b = 0;
// loop iterator
int c = 0;
do
{
// get the last 4 bits in the number
char lowc = static_cast<char>(x & 0x0000000f);
// find the count
b += bc[lowc];
// lose the last four bits
x >>= 4;
++c;
// loop for each possible 4 bit combination,
// or until x is 0 (all significant bits lost)
}
while(c < 8 && x > 0);
return b;
}

Answer 4

Tengo un enfoque ligeramente diferente que debería resolver su problema de memoria. Se basa en el hecho de que la operación bitwise i & -i le da la potencia más pequeña de dos en el número i . Por ejemplo, para i = 5 , i & -i = 1 , para i = 6 , i & -i = 2 . Ahora, para el código:

void countBits(unsigned N) {
for (int i = 0;i < N; i ++)
{
int bits = 0;
for (int j = i; j > 0; j= j - (j&-j))
bits++;
cout <<"Num: "<<i <<" Bits:"<<bits<<endl;
}
}

Espero haber entendido tu pregunta correctamente. Espero que ayude

Edición: Ok, intente esto: esta es una programación dinámica sin usar cada bit en cada número:

void countBits(unsigned N) {
unsigned *arr = new unsigned[N + 1];
arr[0]=0;
for (int i = 1;i <=N; i ++)
{
arr[i] = arr[i - (i&-i)] + 1;
}
for(int i = 0; i <=N; i++)
cout<<"Num: "<<i<<" Bits:"<<arr[i]<<endl;
}

Esperemos que esto funcione mejor.

Answer 5

Varias de las respuestas publicadas hasta ahora utilizan el cambio de bits (solo otra palabra para la división por 2) o el enmascaramiento de bits. Esto me parece un poco engañoso. Lo mismo ocurre con el uso del recuento de bits ''1'' en un patrón de 4 bits y luego se hace coincidir con fragmentos de 4 bits.

¿Qué tal una solución recursiva simple utilizando un árbol binario de bits imaginario? cada rama izquierda contiene un ''0'', cada rama derecha contiene un ''1''. A continuación, realice un primer recorrido en profundidad contando el número de 1 bits en el camino hacia abajo. Una vez que se alcanza la parte inferior del árbol, agregue uno al contador, imprima el número de 1 bits encontrados hasta el momento, retroceda un nivel y repita el ejercicio.

Detenga la recursión cuando el contador llegue al número deseado.

No soy un programador de C / C ++, pero aquí hay una solución REXX que debería traducirse sin mucha imaginación. Tenga en cuenta que el número mágico 32 es solo el número de bits en un largo Sin firmar. Configurarlo a cualquier cosa

/* REXX */
SAY ''Stopping number:''
pull StopNum
Counter = 0
CALL CountOneBits 0, 0
return
CountOneBits: PROCEDURE EXPOSE Counter StopNum
ARG Depth, OneBits
If Depth = 32 then Return /* Number of bits in ULong */
if Counter = StopNum then return /* Counted as high as requested */
call BitCounter Depth + 1, OneBits /* Left branch is a 0 bit */
call BitCounter Depth + 1, OneBits + 1 /* Right branch is a 1 bit */
Return
BitCounter: PROCEDURE EXPOSE Counter StopNum
ARG Depth, OneBits
if Depth = 32 then do /* Bottom of binary bit tree */
say D2X(Counter) ''contains'' OneBits ''one bits''
Counter = Counter + 1
end
call CountOneBits Depth, OneBits
return 

Resultados:

Stopping number:
18
0 contains 0 one bits
1 contains 1 one bits
2 contains 1 one bits
3 contains 2 one bits
4 contains 1 one bits
5 contains 2 one bits
6 contains 2 one bits
7 contains 3 one bits
8 contains 1 one bits
9 contains 2 one bits
A contains 2 one bits
B contains 3 one bits
C contains 2 one bits
D contains 3 one bits
E contains 3 one bits
F contains 4 one bits
10 contains 1 one bits
11 contains 2 one bits

Esta respuesta es razonablemente eficiente en tiempo y espacio.

Answer 6

enum bit_count_masks32
{
one_bits= 0x55555555, // 01...
two_bits= 0x33333333, // 0011...
four_bits= 0x0f0f0f0f, // 00001111....
eight_bits= 0x00ff00ff, // 0000000011111111...
sixteen_bits= 0x0000ffff, // 00000000000000001111111111111111
};
unsigned int popcount32(unsigned int x)
{
unsigned int result= x;
result= (result & one_bits) + (result & (one_bits << 1)) >> 1;
result= (result & two_bits) + (result & (two_bits << 2)) >> 2;
result= (result & four_bits) + (result & (four_bits << 4)) >> 4;
result= (result & eight_bits) + (result & (eight_bits << 8)) >> 8;
result= (result & sixteen_bits) + (result & (sixteen_bits << 16)) >> 16;
return result;
}
void print_range(unsigned int low, unsigned int high)
{
for (unsigned int n= low; unsigned int n<=high; ++n)
{
cout << std::hex << " num = " << xcount << std::dec << " number of 1s = " << popcount32(n) << endl;
}
}