21–30 of 49 posts
As much as I love bit manipulation, I have to say that most (not all) of them don't provide any real performance gain for C/C++ code (only some geeky satisfaction of writing difficult to interpret code!).. e.g. with any decent compiler... * if ((x & 1) == 0) performs same as, if ((x % 2) == 0) * if (x & (1 so on.. on the other hand, i find bit operations really handy when the variables in question are to be treated a…
As much as I love bit manipulation, I have to say that most (not all) of them don't provide any real performance gain for C/C++ code (only some geeky satisfaction of writing difficult to interpret code!).. e.g. with any decent compiler... * if ((x & 1) == 0) performs same as, if ((x % 2) == 0) * if (x & (1 so on.. on the other hand, i find bit operations really handy when the variables in question are to be treated a…
Agreed regarding modulo, but `pow' returns a floating-point number.
Here's a much more comprehensive collection of bit hacks: http://graphics.stanford.edu/~seander/bithacks.html
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)))
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 not execute particularly fast on modern processors. Instruction/cycle counts -- like 3 -- are great when there's no pipeline and no cache, but otherwise pretty much useless. 4. The things you're swapping might be local variables, and when the compiler has -O specified, local variables start getting weird, and "swap" can sometimes be done in zero instructions, namely by the compiler noting that they have now been swapped and using the other one for the rest of the basic block. (or further dominated basic blocks for that matter) 5. If the things you're swapping are in main memory, or even if it's not in L1, you're going to be incurring a cost much greater than the temporary use of a register. (and, if you don't know where they are and it might be main memory, this might dominate the average runtime)
The answer is definitely not "three xors".
Here is a fun challenge for language snobs: implement bit-streams for your favorite language. Here is a simple signature: bitvec read_nbits (unsigned int count, bitstream input); bool write_nbits (unsigned int count,bitvec bits, bitstream output); Then add a multirecord I/O. That is, read a record of bitvecs, each N bits wide, where the length is not given but encoded in the bitstream in this manner: read a bitvec re…
Here is a fun challenge for language snobs: implement bit-streams for your favorite language. Here is a simple signature: bitvec read_nbits (unsigned int count, bitstream input); bool write_nbits (unsigned int count,bitvec bits, bitstream output); Then add a multirecord I/O. That is, read a record of bitvecs, each N bits wide, where the length is not given but encoded in the bitstream in this manner: read a bitvec re…
You wouldn't happen to still have your code? This sounds like an interesting exercise. Maybe you could blog about your implementation and we can compare notes.
Here is a fun challenge for language snobs: implement bit-streams for your favorite language. Here is a simple signature: bitvec read_nbits (unsigned int count, bitstream input); bool write_nbits (unsigned int count,bitvec bits, bitstream output); Then add a multirecord I/O. That is, read a record of bitvecs, each N bits wide, where the length is not given but encoded in the bitstream in this manner: read a bitvec re…
let nthbit (bitContainer:'T) nth : bool = (bitContainer &&& ((1 :> 'T) ) : seq =
let sz = sizeof
bitContainerSeq
|> Seq.map (fun b -> [0..sz]
|> nthbit b
|> Seq.ofArray )
|> Seq.concat
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…
Here is a fun challenge for language snobs: implement bit-streams for your favorite language. Here is a simple signature: bitvec read_nbits (unsigned int count, bitstream input); bool write_nbits (unsigned int count,bitvec bits, bitstream output); Then add a multirecord I/O. That is, read a record of bitvecs, each N bits wide, where the length is not given but encoded in the bitstream in this manner: read a bitvec re…
let nthbit (bitContainer:'T) nth : bool = (bitContainer &&& ((1 :> 'T) ) : seq = let sz = sizeof bitContainerSeq |> Seq.map (fun b -> [0..sz] |> nthbit b |> Seq.ofArray ) |> Seq.concat I think that should do it unfortunatley I'm away from an F# compiler
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.
Earlier quoted context omitted.
let nthbit (bitContainer:'T) nth : bool = (bitContainer &&& ((1 :> 'T) ) : seq = let sz = sizeof bitContainerSeq |> Seq.map (fun b -> [0..sz] |> nthbit b |> Seq.ofArray ) |> Seq.concat I think that should do it unfortunatley I'm away from an F# compiler
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.
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)))
|> bitstream
let bits (bitContainer:'T) : seq =
[0..(sizeof*8)]
|> Seq.ofArray
|> Seq.map (fun nth -> (bitContainer &&& ((1 :> 'T) new System.IO.FileStream('foo.txt')
|> Seq.unfold (fun s -> (s , match s.read with
| -1 -> None
| x -> Some(x)))
|> Seq.map bits
|> Seq.concat