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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
5 Comments »

5 Responses to “Three Bit Hacks”

  1. chaw said
    September 7, 2017 at 1:56 PM

    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
    September 7, 2017 at 2:01 PM

    [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
    September 12, 2017 at 5:11 PM

    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
    September 14, 2017 at 5:44 AM

    Here’s a Haskell version.

    -- 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
    November 10, 2017 at 2:08 PM

    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]

Leave a comment