2 people like it.

Fun with Generic Bit Manipulation

Some generic functions that use bit manipulation. They work for all signed integer types and are faster than the standard functions min, max, abs and sign.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
open LanguagePrimitives

// A simple trick enables genericity below: In F#, the shift amount
// takes into account the lowest bits only. Therefore, shifting right by -1
// results in the maximum shift and the sign bit gets propagated to the whole word.

/// Maximum of zero and the argument for signed integers. A special version using bit manipulation tricks.
let inline maxi0 x = x &&& ~~~(x >>> -1)

/// Minimum of zero and the argument for signed integers. A special version using bit manipulation tricks.
let inline mini0 x = x &&& (x >>> -1)

/// Maximum function for signed integers. A special version using bit manipulation tricks.
/// Has limited numerical range: requires that a - b is representable.
let inline maxi (a : 'a) (b : 'a) : 'a = maxi0 (a - b) + b

/// Minimum function for signed integers. A special version using bit manipulation tricks.
/// Has limited numerical range: requires that a - b is representable.
let inline mini (a : 'a) (b : 'a) : 'a = mini0 (a - b) + b

/// Clamps signed integer x to [a, b] (a <= b). A special version using bit manipulation tricks.
/// Has limited numerical range: requires that a - b, a - x and b - x are representable.
let inline clampi (a : 'a) (b : 'a) (x : 'a) : 'a = maxi a (mini b x)

/// Sign function for signed integers that uses bit manipulation tricks.
let inline signi (x : 'a) : 'a = ((-x >>> -1) &&& GenericOne) + (x >>> -1)

/// Absolute function for signed integers. A special version using bit manipulation tricks.
/// The smallest signed value cannot be negated; the standard function raises an exception,
/// whereas we return it unchanged.
let inline absi (x : 'a) : 'a = let y = x >>> -1 in (x &&& ~~~y) - (x &&& y)

/// Negative indicator function for signed integers. Returns 1 if x < 0, and 0 otherwise.
let inline negativei x = (x >>> -1) &&& GenericOne

/// Positive indicator function for signed integers. Returns 1 if x > 0, and 0 otherwise.
let inline positivei x = (-x >>> -1) &&& GenericOne
module LanguagePrimitives

from Microsoft.FSharp.Core
val maxi0 : x:'a -> 'a (requires member ( >>> ) and member ( &&& ) and member ( ~~~ ))

Full name: Script.maxi0


 Maximum of zero and the argument for signed integers. A special version using bit manipulation tricks.
val x : 'a (requires member ( >>> ) and member ( &&& ) and member ( ~~~ ))
val mini0 : x:'a -> 'a (requires member ( >>> ) and member ( &&& ))

Full name: Script.mini0


 Minimum of zero and the argument for signed integers. A special version using bit manipulation tricks.
val x : 'a (requires member ( >>> ) and member ( &&& ))
val maxi : a:'a -> b:'a -> 'a (requires member ( - ) and member ( + ) and member ( >>> ) and member ( &&& ) and member ( ~~~ ))

Full name: Script.maxi


 Maximum function for signed integers. A special version using bit manipulation tricks.
 Has limited numerical range: requires that a - b is representable.
val a : 'a (requires member ( - ) and member ( + ) and member ( >>> ) and member ( &&& ) and member ( ~~~ ))
val b : 'a (requires member ( - ) and member ( + ) and member ( >>> ) and member ( &&& ) and member ( ~~~ ))
val mini : a:'a -> b:'a -> 'a (requires member ( - ) and member ( + ) and member ( >>> ) and member ( &&& ))

Full name: Script.mini


 Minimum function for signed integers. A special version using bit manipulation tricks.
 Has limited numerical range: requires that a - b is representable.
val a : 'a (requires member ( - ) and member ( + ) and member ( >>> ) and member ( &&& ))
val b : 'a (requires member ( - ) and member ( + ) and member ( >>> ) and member ( &&& ))
val clampi : a:'a -> b:'a -> x:'a -> 'a (requires member ( - ) and member ( + ) and member ( >>> ) and member ( &&& ) and member ( ~~~ ))

Full name: Script.clampi


 Clamps signed integer x to [a, b] (a <= b). A special version using bit manipulation tricks.
 Has limited numerical range: requires that a - b, a - x and b - x are representable.
val x : 'a (requires member ( - ) and member ( + ) and member ( >>> ) and member ( &&& ) and member ( ~~~ ))
val signi : x:'a -> 'a (requires member ( >>> ) and member ( + ) and member ( &&& ) and member ( ~- ) and member get_One)

Full name: Script.signi


 Sign function for signed integers that uses bit manipulation tricks.
val x : 'a (requires member ( >>> ) and member ( + ) and member ( &&& ) and member ( ~- ) and member get_One)
val GenericOne<'T (requires member get_One)> : 'T (requires member get_One)

Full name: Microsoft.FSharp.Core.LanguagePrimitives.GenericOne
val absi : x:'a -> 'a (requires member ( >>> ) and member ( - ) and member ( &&& ) and member ( ~~~ ))

Full name: Script.absi


 Absolute function for signed integers. A special version using bit manipulation tricks.
 The smallest signed value cannot be negated; the standard function raises an exception,
 whereas we return it unchanged.
val x : 'a (requires member ( >>> ) and member ( - ) and member ( &&& ) and member ( ~~~ ))
val y : 'a (requires member ( >>> ) and member ( - ) and member ( &&& ) and member ( ~~~ ))
val negativei : x:'a -> 'a (requires member get_One and member ( >>> ) and member ( &&& ))

Full name: Script.negativei


 Negative indicator function for signed integers. Returns 1 if x < 0, and 0 otherwise.
val x : 'a (requires member get_One and member ( >>> ) and member ( &&& ))
val positivei : x:'a -> 'a (requires member get_One and member ( ~- ) and member ( &&& ) and member ( >>> ))

Full name: Script.positivei


 Positive indicator function for signed integers. Returns 1 if x > 0, and 0 otherwise.
val x : 'a (requires member get_One and member ( ~- ) and member ( &&& ) and member ( >>> ))
Raw view New version

More information

Link:http://fssnip.net/tq
Posted:2 years ago
Author:Sami Perttu
Tags: mathematics , algorithms , functions , optimizations