• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

pcaldeira

[C] Bit interface - Funções para armazenar valores booleanos em bits

6 mensagens neste tópico

Estas funções servem para armazenar variáveis booleanas (em que só dois valores são possíveis) em bits, permitindo poupar muito espaço. Por exemplo, em C, o mais comum é usar-se um int ou um char para o efeito; mas um int pode armazenar apenas um número inteiro, e no entanto tem 32 bits. Estas funções vão permitir armazenar 32 estados numa única variável int.

#define MAX 1000
#include <math.h>

int states[MAX];

//Bit interface
int check_bit(int num)
{
   int pos = (int)pow((double)2, (double)((num-1)%32));
   return (states[(num-1)/32] & pos) ? 1 : 0;
}

void toggle_bit(int num)
{
   int pos = (int)pow((double)2, (double)((num-1)%32));
   states[(num-1)/32] |= pos;
}

Neste caso, as funções suportam vários ints em vez de um único, pelo que basta definir o tamanho do array e as funções localizarão o int em que determinado valor deverá ser armazenado/acedido.

Pode-se usar qualquer outro tipo: basta mudar o tipo do valor retornado pela função check_bit, o tipo do array states e substituir todos os "32" que se encontram no código pelo número de bits que o tipo de dados pretendido ocupa.

A função toggle_bit assinala o bit passado como parâmetro; a função check_bit verifica se o bit passado como parâmetro está assinalado e retorna 1 se sim ou 0 se não.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso continua a usar a memória que ocuparia com os ints...... Só retorna 1 ou 0, mas isso não tem grande utilidade.....

Há maneira de fazer as varáveis ocupar só um bit, com packed structures, só que isso exige muito processamento em troca de memória que talvez não faça falta, nos dias de hoje....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

nDray, mas ele aqui está a usar um int para armazenar 32 estados diferentes, logo no final vai ocupar muito menos do que se usasse 32 ints para o mesmo efeito.

Já agora, as packed structures (bitfields?) ocupam só o que tu defines? Tenho impressão que ocupam o mesmo, apenas estás limitado ao tamanho que definiste.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso continua a usar a memória que ocuparia com os ints...... Só retorna 1 ou 0, mas isso não tem grande utilidade.....

Não percebeste o que o código faz... tipo em vez de termos 64 variáveis bool (64*1 byte) , temos 2 ints ( 2 * 4 bytes = 8bytes) há uma poupança de 8 vezes menos bytes usados. É normal haver um desperdicío.

Essas funções tão um bocado lentas. Em vez de usares o pow usa os shifts ( "<<"  e ">>" ) - não leste o capitulo de operações bit  a bit da usaco ? :cheesygrin:

#define MAX 1000
#include <math.h>

int states[MAX];

//Bit interface
int check_bit(int num)
{
return ( states[(num-1)/32] & ( 1 << ( (num-1)%32) ) ) != 0 ;
}

void toggle_bit(int num)
{
states[(num-1)/32] |= ( 1 << ( (num-1)%32) );
}

Usar as operações bit a bit são muito úteis. Há outro caso que acho mais util: "Temos um conjunto de N elementos e queremos testar todas as hipoteses de usar ou não cada elemento"

Normalmente o N é pequeno  1 <= N <= 20.

	for (i = 0 ; i < (1<<N) ; i++)
{
	// soma = 0
	for (j = 0 ; j < N ; j++)
	{
		if ( ( i & (1 << j) ) )	// bit j = 1
		{
			// calcula obj j
		}
	}
	// check result com soma
}

Como 2^(20-1) = meio milhão, não há problemas com o tempo de execução. Isto é mais útil quando usamos programação dinâmica, mas não me vou alongar mais  :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em resumo, 4 funções para trabalhar com bits:

int check_bit(int & mask , int num)
{
return ( mask & ( 1 << num ) != 0 );
}

void turn_on_bit(int & mask , int num)
{
mask |= ( 1 << num );
}

void turn_off_bit(int & mask , int num)
{
mask &=  ~( 1 << num );
}

void toggle_bit(int & mask , int num)   // 0 -> 1   ,   1 -> 0
{
mask ^= ( 1 << num );
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não li... hehe... E não prestei grande atenção ao código, mas já percebi....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora