Low Level Bit Hacks You Must Know

Post by fleitz » Wed, Oct 20, 2010, 10:56 PM UTC

fleitz wrote: post #30

mahmud wrote: post #29

Earlier quoted context omitted.

This looks magical :-) Are you sure you're decoding bits from an octet stream (normal 8-bit bytes) and not using logical booleans? I ask this because I don't see any bit-manipulation operators, except maybe for "1 :> 'T" which looks like the SML module type casting, but I could be wrong.

Yes very sure. nthbit will extract the nth bit from an integer type. The bitwise logic is the &&& and http://msdn.microsoft.com/en-us/library/dd469495.aspx bitstream turns a sequence of integer types into a sequence of bits. So if you wanted to turn a stream into bits you'd do something like the following. new System.IO.FileStream('foo.txt') |> Seq.unfold (fun s -> (s , match s.read with | -1 -> None | x -> Some(x)))…

  let bitsToBitContainer (s:seq) : seq =
    let sz = sizeof*8
    s
    |> Seq.scan (fun (i,n) x -> (i++,(n Seq.filter (fun (i,n) -> i = sz)
    |> Seq.map (fun (i,n) -> n)

Post by mentat » Wed, Oct 20, 2010, 11:28 PM UTC

cs_loser wrote: post #24

IgorPartola wrote: post #18

Earlier quoted context omitted.

Ha. Next time someone asks how to swap two values at an interview question (I think this is pretty common): #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

Is it pretty common? As someone who does a fair number of software engineer interviews, that's a trick question. The real answer to "swap two vars with no temps" is: 1. Don't be clever in our code base. Use a temp variable. 2. There's various dumb tricks with XOR, and possibly add/subtract if overflows don't break. 3. A sequence of several instructions where each of them requires the result of the previous one may no…

Post by mahmud » Thu, Oct 21, 2010, 1:18 AM UTC

fleitz wrote: post #31

fleitz wrote: post #30

Earlier quoted context omitted.

Yes very sure. nthbit will extract the nth bit from an integer type. The bitwise logic is the &&& and http://msdn.microsoft.com/en-us/library/dd469495.aspx bitstream turns a sequence of integer types into a sequence of bits. So if you wanted to turn a stream into bits you'd do something like the following. new System.IO.FileStream('foo.txt') |> Seq.unfold (fun s -> (s , match s.read with | -1 -> None | x -> Some(x)))…

Just for fun here's the reverse to turn a sequence of booleans into a sequence of integer types (byte,int,long,etc). Note that the length of sequence s must be a multiple of sizeof times 8 let bitsToBitContainer (s:seq ) : seq = let sz = sizeof *8 s |> Seq.scan (fun (i,n) x -> (i++,(n Seq.filter (fun (i,n) -> i = sz) |> Seq.map (fun (i,n) -> n)

Post by leif » Thu, Oct 21, 2010, 1:48 AM UTC

mentat wrote: post #33

cs_loser wrote: post #24

Earlier quoted context omitted.

Is it pretty common? As someone who does a fair number of software engineer interviews, that's a trick question. The real answer to "swap two vars with no temps" is: 1. Don't be clever in our code base. Use a temp variable. 2. There's various dumb tricks with XOR, and possibly add/subtract if overflows don't break. 3. A sequence of several instructions where each of them requires the result of the previous one may no…

Embedded and firmware engineering questions expect this as an answer. Anyone following your advice will not be taken seriously. This is true regardless of whether you're correct factually. Readers of this thread deserve to know that.

    int x, y;
    ...
    SWAP(x, y);
    foo(x, y);

    int x, y;
    ...
    foo(y, x);

Post by leif » Thu, Oct 21, 2010, 3:58 AM UTC

pjscott wrote: post #38

leif wrote: post #37

Earlier quoted context omitted.

3 is actually a quite valid point for embedded. Any swap actually will be expensive when it comes to keeping cache lines clean. The correct answer in that case is just to not swap the variables, and instead swap their uses later on: int x, y; ... SWAP(x, y); foo(x, y); becomes int x, y; ... foo(y, x); (naturally, this is why I still eagerly await the arrival of a C compiler that has macros with LISP power)

In that case, you can get the right behavior by just swapping the variables using a temporary variable. If the compiler is decent, it'll automatically swap their uses later on. I don't know how every compiler works, but if you use Clang (or anything LLVM-based), it converts everything to Single Static Assignment (SSA) form: int x1 = 42, y1 = 666; ... int tmp = x1; x2 = y1; y2 = tmp; // SWAP(x, y) foo(x2, y2); In SSA…