Forums - Open Redstone Engineers
Bit hacks - Printable Version

+- Forums - Open Redstone Engineers (https://forum.openredstone.org)
+-- Forum: Off-Topic (https://forum.openredstone.org/forum-4.html)
+--- Forum: General computing and engineering (https://forum.openredstone.org/forum-66.html)
+--- Thread: Bit hacks (/thread-3840.html)

Bit hacks - jxu - 06-23-2014

Determining if number is power of 2 (excluding 0)

Code:
f = (v & (v - 1)) == 0

Parity of a byte

Code:
bool parity =
  (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;

Modulus by 1 << s:
Code:
m = n & ((1<< s) - 1);


RE: Bit hacks - David - 06-23-2014

I've never used Modulus before but shouldn't

if (x % 2 == 0)

work?

EDIT: Sorry, I'm tired don't mind me being stupid and all.


EDIT 2: Let me try that again.

if ((x & x*-1) == x)

Problem is, this isn't any better than your version or anything. But I just wanted to clean my name.

RE: Bit hacks - redstonewarrior - 06-25-2014

Quote:b * 0x0101010101010101ULL
You lied to us.
Some fun ones from an assignment a while back:

Code:
// Absolute value of an integer. Uses bitmasking fun!
int absVal(int x) {
   int mask = x >> 0x1F;
   return (mask ^ x) + (mask & 1);
}

// Determines if one number is greater than the other, using only basic
// operations and addition. __Works correctly given over/underflow conditions.__
// Uses only 9 operations. I'm proud of this baby, I beat 100+ people with it.
int isGreater(int x, int y) {
  int difference = y + ~x + 1; // y - x. Positive if y > x || overflow.
  int xor = ((y ^ difference) & (x ^ y));
  // -1 iff sign of x != sign of y (difference could OF.)
  return 1 & ((xor ^ (difference)) >> 31);
}

// Another function for identifying powers of two. Works correctly for Two's Complement numbers, I.E. 0x80 won't trigger.
int isPower2(int x) {
  int maskd = x >> 31;
  int sub = x & (x + ~maskd);
  return !(sub | !x); // Edge cases.
}

// More informally, parity can be done without any multiplication / other shenanigans.
// This implementation should be / probably is faster on most CPUs.
Parity:
int a = x;
a ^= a >> 1;
a ^= a >> 2;
a ^= a >> 4;
// Continue logarithmically for wider words...
return a & 1;

All of these functions are written using only assignment, bitwise operators, left/right shift, and addition. There is no control logic, function calls, etc.
:3

RE: Bit hacks - jxu - 06-25-2014

Log base 2 of IEEE 32 bit float

Code:
const int r;
              
int c;        
c = *(const int *) &v;
c = ((((c - 0x3f800000) >> r) + 0x3f800000) >> 23) - 127;



Integer log base 10 of an integer

This one is amazing

Code:
unsigned int v;
int r;        
int t;          

static unsigned int const PowersOf10[] =
    {1, 10, 100, 1000, 10000, 100000,
     1000000, 10000000, 100000000, 1000000000};

t = (IntegerLogBase2(v) + 1) * 1233 >> 12;
r = t - (v < PowersOf10[t]);