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.

Advertisements

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

    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

    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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: