Bitowa reprezentacja liczb całkowitych

Kilka przydatnych funkcji w różnych językach których wspólną cechą jest pełniona zadanie – wszystkie tworzą binarną reprezentację liczb całkowitych. Zanim przejdę do konkretów (tj kodu źródłowogo) trochę teorii ;P. Sprawdzenie, czy n-ty bit liczby całkowitej w reprezentacji dwójkowej x jest zapalony można zasadniczo wykonać na trzy sposoby – jeden dobry i dwa teoretycznie dobre. Dwie teoretycznie dobre to

  • sprawdzenie czy zapalony jest n-ty bit przez operację koniunkcji bitowej z maską 1 << n
     x & (1 << n) 
  • przesunięcie bitowe x o bitsof(x) - n miejsc w lewo i sprawdzenie, czy zapalony jest najstarszy bit
     (x << n ) & 1 << (bitsof(x) - 1) 

gdzie bitsof(x) ≡ sizeof(type(x)) * BITS_PER_BYTE

Powyższe metody jednak nie są uniwersalne. W większości przypadków typów i języków zadziałają poprawnie. Ale wyobraźmy sobie taką sytuację w języku C++

#define IS_BIT_SET(x, n) ((x)  &  (1 << (n)))
long long x = 1;
bool is32ndBitSet = IS_BIT_SET(x,32); // TRUE, absurd !

Przyczyna błędu jest oczywista, i na całą sytuację prawdopodobnie zwróci nam uwagę kompilator odpowiednim ostrzeżeniem ( w przypadku MSVC będzie to C4334 ). Makro to można naprawić

#define IS_BIT_SET(x, n) ((x)  &  (1LL << (n)))

ale można też spróbować czegoś innego

  • przesunięcie bitowe x o n miejsc w prawo i sprawdzenie, czy najmłodzy bit jest zapalony
     (x >> n) & 0x1
C++
#include <string>

#define IS_BIT_SET(x, n) ((x)  &  (1LL << (n)))
#define SET_BIT(x, n)    ((x) |=  (1LL << (n)))
#define UNSET_BIT(x, n)  ((x) |= ~(1LL << (n)))


template<typename T>
std::string toBinStr(T x) {
	std::string s;
	int bits = sizeof(T) * 8;
	for(int b=bits-1;  b>=0; --b) {
		s+=IS_BIT_SET(x,b)?'1':'0';
	}
	return s;
}
Python
def to_bin_str(x):
	import types
	if type(x) is types.IntType: bits = 32;
	else: raise "Argument must by int type!"
	mask = 1 << bits - 1
	return ''.join('0' if x<<shift & mask == 0 else '1' for shift in range(0,bits))
C#
class BinUtil
{
	public static string toBinStr(int x)
	{
		int bits = 32;
		StringBuilder sb = new StringBuilder(bits);
		for(int i=bits - 1; i>=0 ; i--)
		{
			sb.Append( (x >> i & 0x1 )== 0? "0":"1");
		}
		
		return sb.ToString();
	}
	public static string toBinStr(uint x)
	{
		int bits = 32;
		StringBuilder sb = new StringBuilder(bits);
		for(int i=bits - 1; i>=0 ; i--) {
			sb.Append( (x >> i & 0x1 )== 0? "0":"1");
		}
		
		return sb.ToString();		
	}
	public static string toBinStr(long x)
	{
		int bits = 64;
		StringBuilder sb = new StringBuilder(bits);
		for(int i=bits - 1; i>=0 ; i--) {
			sb.Append( (x >> i & 0x1 )== 0? "0":"1");
		}
		return sb.ToString();			
	}
	public static string toBinStr(ulong x)
	{
		int bits = 64;
		StringBuilder sb = new StringBuilder(bits);
		for(int i=bits - 1; i>=0 ; i--) {
			sb.Append( (x >> i & 0x1 )== 0? "0":"1");
		}
		return sb.ToString();			
	}		
	public static string toBinStr(byte b)
	{
		int bits = 8;
		StringBuilder sb = new StringBuilder(bits);
		for(int i=bits - 1; i>=0 ; i--){
			sb.Append( (b >> i & 0x1 )== 0? "0":"1");
		}
		
		return sb.ToString();		
	}
}
PS

Tytuł posta może być trochę mylący co do jego treści, ale przecież każdy wie dlaczego int i = -1 ≡ 11111111111111111111111111111111b, prawda?

PS PS

Chyba, że procesor nie stosuje arytmetyki uzupełnień do dwójki. Wtedy oczywiście powyższe stwierdzenie nie jest prawdziwe.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s