49 people like it.

Bit manipulation methods

Bit manipulation methods

 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: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 
74: 
75: 
76: 
77: 
78: 
79: 
80: 
81: 
82: 
83: 
84: 
85: 
86: 
87: 
88: 
89: 
90: 
91: 
(*
  2s complement, i.e. invert each bit and add 1
  ex. 5 = 00101 (5) -> 11010 -> 11010 + 1 - > 11011 = -5 
  ex. 16 = 0b10000 -> ~16+1=-16 = -0b10000 (11111111111111111111111111110000 count=28)
*)
type System.Int32 with                        // x=this
  (* bit manipulation methods *)
  member x.shrl =  int (uint32 x >>> 1)     // logical right shift 
  member x.shrln i =  int (uint32 x >>> i)  // logical right shift by n positions
  member x.isset i = x &&& (1 <<< i) <> 0     // test if bit set at a specified position 
  member x.get i = x &&& (1 <<< i) <> 0   
  member x.set i = x ||| (1 <<< i)            // set bit to 1 
  member x.unset i = x &&& ~~~(1 <<< i)       // set bit from 0 
  member x.flip i = (x ^^^ (1 <<< i))       // change bit  
  member x.rev =                              // reverse bits
    let rec go b i acc =
      if i = 32 then acc else go (b>>>1) (i+1) ((acc <<< 1) ||| (b &&& 1))
    go x 0 0
  member x.count =                            // count bits set to 1
    let rec go b acc = if b = 0 then acc else go (b &&& (b-1)) (acc+1) //sparse count
    //if b = 0 then acc else go (b.shrl) (acc + (b &&& 1)) //add res of calc
    go x 0
  member x.count_dense = // The loop will execute once for each unset bit
    32 - ((~~~x).count)  //do sparse count
    
  //as opposed to diff: 0101&(~1100)=0101&0011=0001 xor returns mutual difference: 0101^1100=1001
  member x.diff y = x &&& (~~~y)        // subtract y from x
  member x.subset y = (x &&& y)=x             // x &&& (~~~ super) = 0  //must be in Bitmap module
  member x.propersubset y = (x<y) && ((x &&& y)=x)
  member x.rotateLeft r = (x<<<r) ||| (x>>>(32-r)) 
  member x.rotateRight r = (x>>>r) ||| (x<<<(32-r))
  member x.rotate r = if r > 0 then x.rotateLeft r else x.rotateRight (-r)
  member x.contains_zero_byte = ((x-0x01010101)^^^x) &&& (~~~x) &&& 0x80808080
  member x.rightmost_one = x &&& (-x)
  member x.rightmost_zero = (x ^^^ (x+1)) &&& ~~~x
  member x.leftmost_one = //??
    let mutable y = 0
    y <- x ||| (x>>>1)
    y <- y ||| (y>>>2)
    y <- y ||| (y>>>4)
    y <- y ||| (y>>>8)
    y <- y ||| (y>>>16)
    //y <- y ||| (y>>>32)
    y ^^^ (y>>>1)
  member x.leftmost_zero = x.leftmost_one <<< 1 //??
  member x.rightmost_index = // index of lowest bit set
    let mutable r = 0
    let y = x &&& -x // isolate lowest bit
    if y &&& 0xffff0000 <> 0 then r <- r + 16
    if y &&& 0xff00ff00 <> 0 then r <- r + 8
    if y &&& 0xf0f0f0f0 <> 0 then r <- r + 4
    if y &&& 0xcccccccc <> 0 then r <- r + 2
    if y &&& 0xaaaaaaaa <> 0 then r <- r + 1
    r
  member x.leftmost_index = 
    if 0=x then 0
    else
        let mutable r = 0
        let mutable y = x
        if y &&& 0xffff0000 <> 0 then y <- y >>> 16; r <- r + 16
        if y &&& 0x0000ff00 <> 0 then y <- y >>> 8; r <- r + 8
        if y &&& 0x000000f0 <> 0 then y <- y >>> 4; r <- r + 4
        if y &&& 0x0000000c <> 0 then y <- y >>> 2; r <- r + 2
        if y &&& 0x00000002 <> 0 then r <- r + 1
        r

  (* bit coersion methods *)
  member x.toHex = sprintf "0x%x" x           // to hexadecimal
  member x.toBits = System.Convert.ToString(x, 2).PadLeft(32, '0') // to binary   
  member x.toResizeArray =                    // to Resizable array of positions set to 1
    let array = ResizeArray()
    for i=0 to 31 do
      if x.isset i then array.Add(i)
    array        
  member x.toArray =                          // to array of positions set to 1
    let res = x.toResizeArray
    res.ToArray()
  member x.toList =                           // to list of positions set to 1
    let res = x.toResizeArray
    Array.toList (res.ToArray())
  member x.toSeq =                            // to seq of positions set to 1
    let res = x.toResizeArray
    Array.toSeq (res.ToArray())
  
  (* bit print methods *)
  member x.print = printf "%A" x 
  member x.display =                          // helper to show bits
    x.toArray |> Seq.iter(fun i -> printf "%A " i)

  (* misc methods *)
  member x.abs = (x ^^^ (x >>> 31)) - (x >>> 31) //3000% faster than standard math.abs
namespace System
type Int32 =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 3 overloads
    static val MaxValue : int
    static val MinValue : int
    static member Parse : s:string -> int + 3 overloads
    static member TryParse : s:string * result:int -> bool + 1 overload
  end

Full name: System.Int32
val x : System.Int32
member System.Int32.shrl : int

Full name: Script.shrl
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
Multiple items
val uint32 : value:'T -> uint32 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.uint32

--------------------
type uint32 = System.UInt32

Full name: Microsoft.FSharp.Core.uint32
member System.Int32.shrln : i:int32 -> int

Full name: Script.shrln
val i : int32
member System.Int32.isset : i:int32 -> bool

Full name: Script.isset
member System.Int32.get : i:int32 -> bool

Full name: Script.get
member System.Int32.set : i:int32 -> System.Int32

Full name: Script.set
member System.Int32.unset : i:int32 -> System.Int32

Full name: Script.unset
member System.Int32.flip : i:int32 -> System.Int32

Full name: Script.flip
member System.Int32.rev : int

Full name: Script.rev
val go : (int -> int -> int -> int)
val b : int
val i : int
val acc : int
member System.Int32.count : int

Full name: Script.count
val go : (int -> int -> int)
member System.Int32.count_dense : int

Full name: Script.count_dense
member System.Int32.diff : y:System.Int32 -> System.Int32

Full name: Script.diff
val y : System.Int32
member System.Int32.subset : y:System.Int32 -> bool

Full name: Script.subset
member System.Int32.propersubset : y:System.Int32 -> bool

Full name: Script.propersubset
member System.Int32.rotateLeft : r:int32 -> System.Int32

Full name: Script.rotateLeft
val r : int32
member System.Int32.rotateRight : r:int32 -> System.Int32

Full name: Script.rotateRight
member System.Int32.rotate : r:int -> System.Int32

Full name: Script.rotate
val r : int
member System.Int32.rotateLeft : r:int32 -> System.Int32
member System.Int32.rotateRight : r:int32 -> System.Int32
member System.Int32.contains_zero_byte : System.Int32

Full name: Script.contains_zero_byte
member System.Int32.rightmost_one : System.Int32

Full name: Script.rightmost_one
member System.Int32.rightmost_zero : System.Int32

Full name: Script.rightmost_zero
member System.Int32.leftmost_one : int

Full name: Script.leftmost_one
val mutable y : int
member System.Int32.leftmost_zero : int

Full name: Script.leftmost_zero
property System.Int32.leftmost_one: int
member System.Int32.rightmost_index : int

Full name: Script.rightmost_index
val mutable r : int
member System.Int32.leftmost_index : int

Full name: Script.leftmost_index
val mutable y : System.Int32
member System.Int32.toHex : string

Full name: Script.toHex
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
member System.Int32.toBits : string

Full name: Script.toBits
type Convert =
  static val DBNull : obj
  static member ChangeType : value:obj * typeCode:TypeCode -> obj + 3 overloads
  static member FromBase64CharArray : inArray:char[] * offset:int * length:int -> byte[]
  static member FromBase64String : s:string -> byte[]
  static member GetTypeCode : value:obj -> TypeCode
  static member IsDBNull : value:obj -> bool
  static member ToBase64CharArray : inArray:byte[] * offsetIn:int * length:int * outArray:char[] * offsetOut:int -> int + 1 overload
  static member ToBase64String : inArray:byte[] -> string + 3 overloads
  static member ToBoolean : value:obj -> bool + 17 overloads
  static member ToByte : value:obj -> byte + 18 overloads
  ...

Full name: System.Convert
System.Convert.ToString(value: string) : string
   (+0 other overloads)
System.Convert.ToString(value: System.DateTime) : string
   (+0 other overloads)
System.Convert.ToString(value: decimal) : string
   (+0 other overloads)
System.Convert.ToString(value: float) : string
   (+0 other overloads)
System.Convert.ToString(value: float32) : string
   (+0 other overloads)
System.Convert.ToString(value: uint64) : string
   (+0 other overloads)
System.Convert.ToString(value: int64) : string
   (+0 other overloads)
System.Convert.ToString(value: uint32) : string
   (+0 other overloads)
System.Convert.ToString(value: int) : string
   (+0 other overloads)
System.Convert.ToString(value: uint16) : string
   (+0 other overloads)
member System.Int32.toResizeArray : System.Collections.Generic.List<int>

Full name: Script.toResizeArray
Multiple items
val array : System.Collections.Generic.List<int>

--------------------
type 'T array = 'T []

Full name: Microsoft.FSharp.Core.array<_>
type ResizeArray<'T> = System.Collections.Generic.List<'T>

Full name: Microsoft.FSharp.Collections.ResizeArray<_>
member System.Int32.isset : i:int32 -> bool
System.Collections.Generic.List.Add(item: int) : unit
member System.Int32.toArray : int []

Full name: Script.toArray
val res : System.Collections.Generic.List<int>
property System.Int32.toResizeArray: System.Collections.Generic.List<int>
System.Collections.Generic.List.ToArray() : int []
member System.Int32.toList : int list

Full name: Script.toList
module Array

from Microsoft.FSharp.Collections
val toList : array:'T [] -> 'T list

Full name: Microsoft.FSharp.Collections.Array.toList
member System.Int32.toSeq : seq<int>

Full name: Script.toSeq
val toSeq : array:'T [] -> seq<'T>

Full name: Microsoft.FSharp.Collections.Array.toSeq
member System.Int32.print : unit

Full name: Script.print
val printf : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printf
member System.Int32.display : unit

Full name: Script.display
property System.Int32.toArray: int []
module Seq

from Microsoft.FSharp.Collections
val iter : action:('T -> unit) -> source:seq<'T> -> unit

Full name: Microsoft.FSharp.Collections.Seq.iter
member System.Int32.abs : System.Int32

Full name: Script.abs
Raw view New version

More information

Link:http://fssnip.net/Q
Posted:8 years ago
Author:Andrei Logunov
Tags: bits , bit manipulation