## Three Bit Hacks

### September 5, 2017

We have three problems today that involve twiddling bits. In all three cases you are not permitted to perform any branching operation (so no if-else statement) nor are you permitted to perform a loop; you must write a single statement that performs the requested task:

1) Determine the absolute value of an integer.

2) Determine if an integer is a power of 2.

3) Determine the minimum and maximum of two integers.

The restrictions on branching and loops are useful for modern CPUs that have instruction caches that you want to stay inside for speed.

Your task is to write the three bit hacks described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 5 Responses to “Three Bit Hacks”

1. chaw said

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)))) ```

2. chaw said

[Retrying with hopefully better formatting.]

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)))) ```

3. Daniel said

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)].

```/* bithacks.s */

.section .text

# int power2(int x);
#   = x && !(x & (x-1))
.globl power2
power2:
pushl %ebp
movl %esp, %ebp
# %eax = %ecx = x
movl 8(%ebp), %eax
movl %eax, %ecx
# %ecx = %eax & (%ecx - 1)
decl %ecx
andl %eax, %ecx
movl \$0, %edx
testl %ecx, %ecx
setz %dl
movl \$0, %ecx
testl %eax, %eax
setnz %cl
# %edx = %eax && %ecx
andl %ecx, %edx
movl %edx, %eax
movl %edx, %eax
# Restore old base pointer
movl %ebp, %esp
popl %ebp
ret

# int absolute(int x);
#   = (2*(x>=0)-1)*x
.globl absolute
absolute:
pushl %ebp
movl %esp, %ebp
# %eax = x
movl 8(%ebp), %eax
# %ecx = %eax >= 0
movl \$0, %ecx
cmpl \$0, %eax
setns %cl
# %ecx = (2 * %ecx) - 1
# (%ecx becomes -1 for x < 0, and 1 otherwise)
imull \$2, %ecx
decl %ecx
# %eax *= %ecx
imull %ecx, %eax
# Restore old base pointer
movl %ebp, %esp
popl %ebp
ret

# int minimum(int a, int b);
#   = b ^ ((a ^ b) & -(a<b))
.globl minimum
minimum:
pushl %ebp
movl %esp, %ebp
# %eax = a, %ecx = b
movl 8(%ebp), %eax
movl 12(%ebp), %ecx
# %edx = -(a<b)
movl \$0, %edx
cmpl %ecx, %eax
sets %dl
negl %edx
# %eax = %eax ^ %ecx
xorl %ecx, %eax
# %eax = %eax & %edx
andl %edx, %eax
# %eax = %eax ^ %ecx
xorl %ecx, %eax
# Restore old base pointer
movl %ebp, %esp
popl %ebp
ret

# int maximum(int a, int b);
#   = a ^ ((a ^ b) & -(a<b))
.globl maximum
maximum:
pushl %ebp
movl %esp, %ebp
# %eax = b, %ecx = a
movl 8(%ebp), %ecx
movl 12(%ebp), %eax
# %edx = -(a<b)
movl \$0, %edx
cmpl %eax, %ecx
sets %dl
negl %edx
# %eax = %ecx ^ %eax
xorl %ecx, %eax
# %eax = %eax & %edx
andl %edx, %eax
# %eax = %ecx ^ %eax
xorl %ecx, %eax
# Restore old base pointer
movl %ebp, %esp
popl %ebp
ret
```

Here’s a C program that calls the functions.

```/* main.c */

#include <stdio.h>

int absolute(int x);
int power2(int x);
int minimum(int a, int b);
int maximum(int a, int b);

int main(int argc, char* argv[]) {
// Test power2
printf("Powers of 2 from 0 to 128\n");
for (int i = 0; i <= 128; ++i) {
if (power2(i)) printf("%d\n", i);
}

// Test absolute
printf("\n");
for (int i = -3; i <= 3; ++i) {
printf("abs(%2d) = %d\n", i, absolute(i));
}

// Test minimum
printf("\n");
for (int i = 0; i <= 2; ++i) {
for (int j = 0; j <= 2; ++j) {
printf("min(%d,%d) = %d\n", i, j, minimum(i,j));
}
}

// Test maximum
printf("\n");
for (int i = 0; i <= 2; ++i) {
for (int j = 0; j <= 2; ++j) {
printf("max(%d,%d) = %d\n", i, j, maximum(i,j));
}
}
}
```

Here’s example usage.

```\$ as --32 -o bithacks.o bithacks.s
\$ gcc -m32 -o main main.c bithacks.o
\$ ./main
```

Output:

```Powers of 2 from 0 to 128
1
2
4
8
16
32
64
128

abs(-3) = 3
abs(-2) = 2
abs(-1) = 1
abs( 0) = 0
abs( 1) = 1
abs( 2) = 2
abs( 3) = 3

min(0,0) = 0
min(0,1) = 0
min(0,2) = 0
min(1,0) = 0
min(1,1) = 1
min(1,2) = 1
min(2,0) = 0
min(2,1) = 1
min(2,2) = 2

max(0,0) = 0
max(0,1) = 1
max(0,2) = 2
max(1,0) = 1
max(1,1) = 1
max(1,2) = 2
max(2,0) = 2
max(2,1) = 2
max(2,2) = 2
```
4. Globules said

```-- The following functions are based on descriptions from the book "Hacker's
-- Delight - Second Edition" by Henry S. Warren, Jr.

{-# LANGUAGE MagicHash #-}

import Data.Bits
import Data.Bool
import GHC.Exts
import Prelude hiding (abs)

-- The absolute value of the argument.  The only exception is when the argument
-- is the smallest value of a signed number, in which case that value is
-- returned.
abs :: (Num a, FiniteBits a) => a -> a
abs x = let y = x `shiftR` (finiteBitSize x) in (x + y) `xor` y

-- True if and only if n is a power of 2.
isPow2 :: Bits a => a -> Bool
isPow2 x = popCount x == 1

-- The minimum and maximum of two values.
--
-- Internally we use the doz function, which is "difference or zero".  That is,
-- doz x y is x - y if x > y, otherwise it's 0.
minMax :: (Bits a, Ord a, Num a) => a -> a -> (a, a)
minMax x y = let d = doz x y in (x - d, y + d)
where doz x y = (x - y) .&. bool 0 (-1) (x >= y)

-- A similar function, but written using GHC's primitive functions on unlifted
-- Ints (in case you think the bool function is a little too much like
-- branching).
minMax' :: Int -> Int -> (Int, Int)
minMax' x y = let d = doz x y in (x - d, y + d)
where doz (I# x) (I# y) = I# ((x -# y) `andI#` (negateInt# (x >=# y)))

test :: (Show a, Show b) => String -> (a -> b) -> a -> IO ()
test name fn val = putStrLn \$ name ++ " " ++ show val ++ " = " ++ show (fn val)

main :: IO ()
main = do
test "abs" abs (1234 :: Int)
test "abs" abs (-123 :: Int)
test "abs" abs (minBound :: Int) -- oops!

test "isPow2" isPow2 (0 :: Int)
test "isPow2" isPow2 (32 :: Int)
test "isPow2" isPow2 (33 :: Int)

test "minMax" (uncurry minMax) ((-33, 5) :: (Int, Int))
test "minMax" (uncurry minMax) ((5, -33) :: (Int, Int))
test "minMax" (uncurry minMax) ((-33, -33) :: (Int, Int))

test "minMax'" (uncurry minMax') ((-33, 5) :: (Int, Int))
test "minMax'" (uncurry minMax') ((5, -33) :: (Int, Int))
test "minMax'" (uncurry minMax') ((-33, -33) :: (Int, Int))
```
```\$ ./bitHacks
abs 1234 = 1234
abs -123 = 123
abs -9223372036854775808 = -9223372036854775808
isPow2 0 = False
isPow2 32 = True
isPow2 33 = False
minMax (-33,5) = (-33,5)
minMax (5,-33) = (-33,5)
minMax (-33,-33) = (-33,-33)
minMax' (-33,5) = (-33,5)
minMax' (5,-33) = (-33,5)
minMax' (-33,-33) = (-33,-33)
```
5. psitronic said

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]