## Three Bit Hacks

### September 5, 2017

We give solutions in C, since bit-twiddling in Scheme is ugly.

**First: Absolute value.**

int v; // find the absolute value of v (v>0)*v+(v<0)*-v);

**Second: IsPowerOfTwo.**

int v; // determine if v is a power of two // result is 1 if v is a power of two, else 0 v && !(v & (v-1));

**Third: Min/Max of two integers.**

int x, y; // two integers int min, max; // results min = y ^ ((x ^ y) & -(x < y)); max = x ^ ((x ^ y) & -(x < y));

We discussed the absolute value task in a previous exercise, giving a bit-hacking version there. The others you will have to decipher for yourself, which can be enjoyable if you have the right mindset, and is otherwise painful.

You can run the program at https://ideone.com/KztXh3.

Advertisements

Pages: 1 2

Here is some bit-twiddling in Scheme (R7RS + SRFI-143) that I don’t

think is ugly.

;; Caveat: Fails for inputs outside range -2^w ... 2^w - 1, where w is

;; the implementation-dependent fx-width (e.g., 30 for my 32-bit

;; Larceny Scheme setup).

;;; Dependencies

(import (scheme base)

(srfi 143))

;;;Absolute value

(define (abs/b n)

(let ((m (fxarithmetic-shift-right n

(- fx-width 1))))

;; If n is nonnegative, then m = 0 and the following are essentially

;; two no-ops on n, giving n as result.

;; Otherwise (n is negative), m is bitwise all 1s, (i.e., -1

;; in 2s-complement), so we compute:

;; 1s-complement-of-n - -1 = -n (2s compl.)

(- (fxxor n m)

m)))

;;; Power-of-two predicate

;; n must be a positive integer.

(define (power-of-two/b? n)

;; Iff n is a power of two:

;; n has binary form 00...0100...0 and

;; n - 1 has binary form 00...0011...1

(zero? (fxand n (- n 1))))

;;; Min and max

;; a b -> (min a b) (max a b)

(define (min+max/b a b)

(let* ((a-xor-b (fxxor a b))

(m1 (fxarithmetic-shift-right (- a b)

(- fx-width 1)))

(mask (fxand a-xor-b m1)))

;; m1 is bitwise all 1s iff a < b, and all 0s otherwise.

;; So mask is a-xor-b iff a < b (0 otherwise)

;; Then b xor mask gives b xor a xor b = a if a < b

;; and b xor 0 = b o.w.

;; which is the min of a and b as needed. a xor mask is similar, for max.

(values (fxxor b mask)

(fxxor a mask))))

[Retrying with hopefully better formatting.]

Here is some bit-twiddling in Scheme (R7RS + SRFI-143) that I don’t

think is ugly.

Here’s a solution in x86 assembly. The solution is implemented with functions, so the ret instruction is used, but otherwise there are no branching instructions. The power of two, minimum, and maximum functions use bit twiddling approaches from http://graphics.stanford.edu/~seander/bithacks.html. The absolute value function does not use bit twiddling, but rather calculates abs(x) by multiplying x by 1 for x>=0, and by -1 for x<0. The multiple is calculated without branching [abs(x) = x * (2 * (x>=0) – 1)].

Here’s a C program that calls the functions.

Here’s example usage.

Output:

Here’s a Haskell version.

In Python 3:

Absolute value:

absolute = lambda x:(x, -x)[x < 0]

Test for power of 2 (for x > 0):

isPower2 = lambda x:(False,True)[(x & (x – 1)) == 0]

minimum and maximum of two integers:

minimum = lambda x,y: (x,y)[x – y > 0]

maximum = lambda x,y: (x,y)[x – y < 0]