41.5. РЕАЛИЗАЦИЯ СПЕЦИАЛЬНЫХ ФУНКЦИЙ

 
  THIS SECTION IS UNDER CONSTRUCTION  
 


Специальные функции очень важны, часто их реализуют аппаратно в микропроцессорах
и используя их можно довольно хорошо оптимизировать вычисления.

В этой секции расказывается как их проэмулировать если они недоступны
(например не реализованны аппаратно, или ваш язык программирования не поддерживает
такие операции).



  
  Shift Arithmetic Right 
 

Арифметический сдвиг вправо

  



для 32-битной машины в дополнительном коде:

	X >>> N = ((X + 0x80000000) >> N) - (0x80000000 >> N)





  
  Generalized Shift 
 

Реализация функции Generalized Shift для 32-битных архитектур в доболнительном коде:
Generalized shift - функция которая может сдвигать и влева и вправо (в зависимости от
знака аргумента, а так же может сдвигать на большее число бит чем размер операнда,
естественно в этом случае результат будет 0.

unsigned long genshift(unsigned long v, int x)
{
	int	a,b;
	a = (v << x) & -(((unsigned int) x) < 32);
	x = -x;
	b = (v >> x) & -(((unsigned int) x) < 32);
	return	a | b;
}





  
  ABS/NABS 
 

ABS - абсолютная величина (модуль числа)

	ABS(X) = |  X,  X >= 0
		 | -X,  X <  0




NABS - нетативная абсолютная величина числа

	NABS(X) = |  X,  X <= 0
		  | -X,  X >  0




для 32-битной машины в дополнительном коде:

	пусть	Y =  X >>> 31,  тогда

	ABS(X)  = (X ^ Y) - Y  = (X + Y) ^ Y  = X - (2X & Y)
	NABS(X) = Y - (X ^ Y)  = (Y - X) ^ Y  = (2X & Y) - X




  
  Rotate 
 

Rotate Left:
  



	X <-< N = (X << N) | (X >> (32 - N))



Rotate Right:
  


	

	X >-> N = (X >> N) | (X << (32 - N))

  





  
  Sign 
 

	Sign(X) = | -1, X < 0
		  |  0, X = 0
		  |  1, X > 0

для 32-битной машины в дополнительном коде:

	Sign(x) = (X >>> 31) | (-X >> 31)




  
  Population count 
 

  


Population count - возвращает число единичных бит в аргументе
Очень полезная вещь для медийных приложений.
Аппаратная реализация - каскад сумматоров:

  


для 32-битной машины в дополнительном коде:

	int	pop(unsigned x)
	{
		x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
		x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
		x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
		x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
		x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
		return x;
	}

	pop(x) = x - SUM{1,31}(X >> 1)

Интересно посмотреть на график функции Population Count:
  



Дистанция Хэмминга
	dist(X,Y) = pop(X ^ Y)



  
  Четность 
 

  



	parity(X) = XOR{i=0,N-1}(X >> i)

для 32 разрядной машины

	y = x ^ (x >> 1)
	y = y ^ (y >> 2)
	y = y ^ (y >> 4)
	y = y ^ (y >> 8)
	y = y ^ (y >> 16)



  
  Average 
 

	
Unsigned
                     X+Y                          U
	ROUNDTOZERO(-----) = (X & Y) + ((X xor Y) >> 1)
	              2


			 X+Y                          U
	ROUNDTOWARDZERO(-----) = (X | Y) - ((X xor Y) >> 1)
	                  2



  
  Number of Leading Zero 
 

  


 
  THIS SECTION IS UNDER CONSTRUCTION  
 


	nlz(x)

Есть также аналог - number of Leading Ones.




  
  Number of Trailing Zero 
 

 
  THIS SECTION IS UNDER CONSTRUCTION  
 


  


	ntz(x)


	int ntz(unsigned x) 
	{
		unsigned y, bz, b4, b3, b2, b1, b0;
		y = x & -x; // Isolate rightmost 1-bit.

		bz = y ? 0 : 1; // 1 if y = 0.
		b4 = (y & 0x0000FFFF) ? 0 : 16;
		b3 = (y & 0x00FF00FF) ? 0 : 8;
		b2 = (y & 0x0F0F0F0F) ? 0 : 4;
		b1 = (y & 0x33333333) ? 0 : 2;
		b0 = (y & 0x55555555) ? 0 : 1;
		return bz + b4 + b3 + b2 + b1 + b0;
	}


	int ntz(unsigned x) 
	{
		static char table[32] =
			{ 0, 1, 2,24, 3,19, 6,25, 22, 4,20,10,16, 7,12,26,
			  31,23,18, 5,21, 9,15,11, 30,17, 8,14,29,13,28,27 };

		if (x == 0) return 32;
		x = (x & -x) * 0x04D7651F;
		return table[x >> 27];
	}


Есть аналог - number of trailing ones.