Sistemas de Numeração
No cotidiano, o sistema decimal é o padrão predominante, utilizando os algarismos de 0 a 9. Sua base é 10, seguindo a regra de que cada dez unidades em uma posição formam uma unidade na posição imediatamente superior.
No contexto da computação, o sistema binário é fundamental, operando apenas com os dígitos 0 e 1 (base 2). Para facilitar a leitura e representação de grandes sequências binárias, utilizam-se frequentemente os sistemas octal (base 8) e hexadecimal (base 16).
- Octal: Utiliza os dígitos de 0 a 7.
- Hexadeicmal: Utiliza 16 símbolos: 0-9 e as letras A-F (representando os valores de 10 a 15, respectivamente).
De forma genérica, um sistema de base $R$ possui as seguintes características:
- Possui $R$ símbolos distintos, variando de $0$ a $R-1$.
- A contagem segue a regra "atingiu $R$, incrementa a ordem superior".
- O valor de cada dígito é determinado pelo seu peso posicional, definido por $R^i$, onde $i$ é o índice da posição (iniciando em 0 para a unidade inteira mínima).
Qualquer número em uma base $R$ pode ser expresso pela expansão polinomial:
$$N = A_{n-1} \times R^{n-1} + \dots + A_1 \times R^1 + A_0 \times R^0 + A_{-1} \times R^{-1} + \dots + A_{-m} \times R^{-m}$$
Conversão entre Bases
Decimal para Binário
Para converter a parte inteira de um número decimal para binário, utiliza-se o método de divisões sucessivas por 2 até que o quociente seja zero. Os restos das divisões, lidos da última para a primeira, formam o número binário. Para a parte fracionária, utiliza-se a multiplicação sucesssiva por 2, coletando a parte inteira resultante.
Binário para Decimal
A conversão envolve a soma dos produtos de cada dígito pelo seu respectivo peso de base 2 ($2^i$).
Exemplo: Converter $11011.101_2$ para decimal.
$(1 \times 2^4) + (1 \times 2^3) + (0 \times 2^2) + (1 \times 2^1) + (1 \times 2^0) + (1 \times 2^{-1}) + (0 \times 2^{-2}) + (1 \times 2^{-3})$
$= 16 + 8 + 0 + 2 + 1 + 0.5 + 0 + 0.125 = 27.625_{10}$
Exemplos Práticos e Implementações
1. Inversão de Representação Binária
O problema consiste em converter um decimal para binário, inverter a ordem dos bits (ignorando zeros à esquerda no resultado final) e converter de volta para decimal.
#include <stdio.h>
void processar_binario_reverso() {
int num_casos;
if (scanf("%d", &num_casos) != 1) return;
while (num_casos--) {
long long n;
scanf("%lld", &n);
int bits[64];
int total_bits = 0;
if (n == 0) {
printf("0\n");
continue;
}
while (n > 0) {
bits[total_bits++] = n % 2;
n /= 2;
}
long long resultado = 0;
int p = 0;
// Pula zeros que se tornariam iniciais após a inversão
while (p < total_bits && bits[p] == 0) p++;
for (int i = p; i < total_bits; i++) {
resultado = (resultado * 2) + bits[i];
}
printf("%lld\n", resultado);
}
}
int main() {
processar_binario_reverso();
return 0;
}
2. Conversão para Base M (Recursiva)
Implementação de uma função genérica para transformar um número decimal em qualquer base entre 2 e 16.
#include <stdio.h>
const char MAPA_HEX[] = "0123456789ABCDEF";
void imprimir_na_base(int n, int base) {
if (n == 0) return;
imprimir_na_base(n / base, base);
putchar(MAPA_HEX[n % base]);
}
int main() {
int valor, base_destino;
while (scanf("%d %d", &valor, &base_destino) == 2) {
if (valor == 0) {
printf("0\n");
} else {
imprimir_na_base(valor, base_destino);
printf("\n");
}
}
return 0;
}
3. Soma de Hexadecimais
Conversão manual de strings hexadecimais para inteiros decimais para realização de operações aritméticas.
#include <stdio.h>
#include <ctype.h>
long long hex_para_decimal(const char *s) {
long long res = 0;
while (*s) {
int val;
char c = toupper(*s);
if (isdigit(c)) val = c - '0';
else val = c - 'A' + 10;
res = (res * 16) + val;
s++;
}
return res;
}
int main() {
char s1[20], s2[20];
while (scanf("%s %s", s1, s2) == 2) {
printf("%lld\n", hex_para_decimal(s1) + hex_para_decimal(s2));
}
return 0;
}
4. Conversor de Base com Formatação (Base A para Base B)
Um algoritmo que converte um número de uma base arbitrária A para uma base B, limitando o resultado a 7 caracteres (comum em visores de calculadoras antigas).
#include <stdio.h>
#include <string.h>
#include <math.h>
void converter_a_para_b() {
char entrada[15];
int base_origem, base_destino;
while (scanf("%s %d %d", entrada, &base_origem, &base_destino) == 3) {
long long decimal = 0;
for (int i = 0; entrada[i]; i++) {
int v = (entrada[i] >= 'A') ? (entrada[i] - 'A' + 10) : (entrada[i] - '0');
decimal = decimal * base_origem + v;
}
char res[50];
int pos = 0;
if (decimal == 0) res[pos++] = '0';
while (decimal > 0) {
int resto = decimal % base_destino;
res[pos++] = (resto < 10) ? (resto + '0') : (resto - 10 + 'A');
decimal /= base_destino;
}
if (pos > 7) {
printf("%7s\n", "ERROR");
} else {
for (int i = 0; i < 7 - pos; i++) putchar(' ');
for (int i = pos - 1; i >= 0; i--) putchar(res[i]);
putchar('\n');
}
}
}
5. Sistema de Contagem Especial (Remoção de Dígitos)
Neste cenário, os dígitos 3 e 7 são ignorados. O sistema comporta-se como uma base 8, onde os símbolos disponíveis são mapeados para [0, 1, 2, 3, 4, 5, 6, 7].
#include <stdio.h>
long long normalizar_w_para_decimal(int n) {
long long dec = 0;
long long pot = 1;
while (n > 0) {
int d = n % 10;
if (d > 7) d -= 2;
else if (d > 3) d -= 1;
dec += d * pot;
pot *= 8;
n /= 10;
}
return dec;
}
int main() {
int x, y;
if (scanf("%d %d", &x, &y) == 2) {
printf("%lld\n", normalizar_w_para_decimal(y) - normalizar_w_para_decimal(x) + 1);
}
return 0;
}
6. Soma dos Quadrados dos Dígitos dos Divisores
Calcula a soma dos quadrados de cada dígito (na base M) de todos os divisores de um número N.
#include <stdio.h>
#include <math.h>
long long soma_quadrados_base_m(int n, int m) {
long long soma = 0;
while (n > 0) {
int d = n % m;
soma += d * d;
n /= m;
}
return soma;
}
int main() {
int n, m;
while (scanf("%d %d", &n, &m) == 2) {
long long total_geral = 0;
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
total_geral += soma_quadrados_base_m(i, m);
if (i * i != n) {
total_geral += soma_quadrados_base_m(n / i, m);
}
}
}
if (total_geral == 0) {
printf("0\n");
continue;
}
char buffer[64];
int p = 0;
while (total_geral > 0) {
int r = total_geral % m;
buffer[p++] = (r < 10) ? (r + '0') : (r - 10 + 'A');
total_geral /= m;
}
for (int i = p - 1; i >= 0; i--) putchar(buffer[i]);
printf("\n");
}
return 0;
}