Abstracting the Bitwise abstraction
-
Company I have worked for in the past had some code for updating some flags displayed to the user elsewhere.
The flags were set in one method which was then called elsewhere, rather than having a separate boolean parameter for the ridiculous number of flags dealt with (4) the method was slightly "smart" in that it took the values as an integer to make Bitwise comparisons. To add to the clever, you also passed a bitmask, so that you could configure which flags you had data for at this moment and set only those.
So for example, you have 4 flags with values 1, 2, 4, 8. You have data for 2 and 4, your mask would be 6.
Anyway, setting aside whether this is a valuable abstraction, the code which sets the flags then creates an if then else chain which renders the entire abstraction pointless, sets up each flag individually and then calls the method to set that one flag.
-
Have an object that keeps track of which properties were set?
-
Bit Masked flags have their place. Unable to just the WTFffyness without the actual code...
-
Bit Masked flags have their place. Unable to just the WTFffyness without the actual code...
I agree with the first sentence. However, this ...
the code which sets the flags then creates an if then else chain which renders the entire abstraction pointless, sets up each flag individually and then calls the method to set that one flag.
... is a WTF.
-
I agree with the first sentence. However, this ...
the code which sets the flags then creates an if then else chain which renders the entire abstraction pointless, sets up each flag individually and then calls the method to set that one flag.
... is a WTF.How many times have we seen someone talk about code, and miss something inherent in the design..at which point the WTF becomes the poster rather than the code????
NOT saying this is what is happening, but without the code it is impossible to tell..it is the phrasing of the second paragraph that makes me suspect....
-
ridiculous number of flags dealt with (4)
4 isn't a ridiculous number of flags. 4,000 is ridiculous, but 4 is really quite reasonable.
-
The bit masking is fine, it makes a lot of sense in many situations, what doesn't is going to all the effort of setting such a method up, and encoding all the flags as a single value, with only 4 values to work with, and then ignoring that, calling the method 4 times one after another to set the values individually.
It's a WTF to invest in a mask based solution if you are working with just a couple of values, unless you are working with external code or constraints which lend themselves to masking. It's even more of a WTF having set all that up, to ignore a significant amount of the benefits provided
-
woosh or woosh baiting?
-
…oh for fuck's sake… that's two days in a row I whooshed badly
-
Sounds like something that should be
#define bm_set(field, mask, value) ((field) = (field) & ~(mask) | (value))
though I usually prefer doing that stuff direct, or via
#define bm_set(field, bit) ((field) |= 1 << (bit))
which can be extended to arbitrary-width fields.
-
The former supports setting multiple field in one call....
-
True. If you actually get a subset of flags from somewhere else, then the helper may be useful. But as mentioned, I prefer doing that kind of fiddling direct, as I do not consider
field &= ~DEFINED_FLAG
orfield |= DEFINED_FLAG
to be so complex they need functions/defines.
-
4,000 is ridiculous
Anything over 32 tends to be difficult to address with an int as a bitmask. I've used longs (actually BIGINT as it was in SQL) for up to 64 flags before
-
Bit Masked flags have their place. Unable to just the WTFffyness without the actual code...
Hmm, trying to determine what was meant. Some options:
Bit Masked flags have their place. Unable to justify the WTFffyness without the actual code...
Bit Masked flags have their place. Unable to
justjudge the WTFffyness without the actual code...I'm betting on the second.
-
###quick quiz
How do you flip 0b1100 to 0b0011 only using bitwise operation.
Another example
correct 0b10101 => 0b01010
wrong0b10101 => 0b111010101.solution should work on any 8bit number.
2. no control flowis it possible if yes how?
-
If the person reading your code doesn't know how those operators work, they should either look it up or they have no right to complain that they don't know.
The only reason I can think of where you'd have a function/define for a single operation is if you were planning to change it in the future and didn't want to break things. And even then, it only works for statically compiled libraries if you use a define because otherwise you break anything compiled with an older version of the library.
-
My point exactly. The only thing that should be #defined is the name of the flag, because 0x01, 0x02, 0x04, etc… are magic numbers.
-
Not sure what you want exactly. Flip bits only up to and including the most significant set bit?
Probably possible. There's an incredible number of weird bitfiddlies you can do without conditional logic.
-
###quick quiz
How do you flip 0b1100 to 0b0011 only using bitwise operation.
Another example
<ins>correct</ins> 0b10101 => 0b01010
<del>wrong</del> 0b10101 => 0b111010101.solution should work on any 8bit number.
2. no control flowis it possible if yes how?
Quick, sloppy answer:
BitArray bits = new BitArray{1,1,0,0}; BitArray xVal = new BitArray(bits.Count, true); BitArray inverted = bits.Xor(xVal);
Based on my interpretation of the question, I win!
-
Flip bits only up to and including the most significant set bit?
yes that.
BitArray bits = new BitArray{1,1,0,0};
BitArray xVal = new BitArray(bits.Count, true);BitArray inverted = bits.Xor(xVal);
I said bitwise only no sorcery allowed
-
He did
~bits
basically.Here's my solution to a different problem:
(x>>7)&1 | (x>>5)&2 | (x>>3)&4 | (x>>1)&8 | (x<<1)&16 | (x<<3)&32 | (x<<5)&64 | (x<<7)&128
-
Here's my solution to a different problem:
The cat went to the store second because the mule's sack wasn't full of rice anymore.
-
Well you can do practically anything with bitwise. Number of bits set, for example:
x = (x & 0b10101010) >> 1 + (x & 0b01010101); x = (x & 0b11001100) >> 2 + (x & 0b00110011); x = (x & 0b11110000) >> 4 + (x & 0b00001111);
IMO logical shifts are bitwise. Addition can be implemented using bitwise operations only; doing so is left as an exercise to the
readergoogler
-
I said bitwise only no sorcery allowed
The only "sorcery" was in assembling the necessary objects.
Fine, no code?
0b1100 XOR 0b1111
Or do you not consider that to be bitwise?
-
This should do it.
x ^ (x | x>>1 | x>>2 | x>>3 | x>>4 | x>>5 | x>>6 | x>>7)
I'll call it the "smear" technique.
-
; in - eax
; out - ecx
; trash - ebx
bsr ebx, eax # Bit scan reverse - find index of highest 1 bit
inc ebx # ebx++
mov ecx, $1 # ecx = 1
shl ecx, ebx # ecx = 1 << ebx
dec ecx # ecx = (1 << ebx) - 1
xor ecx, eax # ecx ^= inputI've got a critical chain 5 instructions long ( ͡° ͜ʖ ͡°)
-
XOR with -1?
-
XOR with -1?
That was my thought, but it fails his test #2, as he wants to flip only 4 or 5 bits instead of the full 8 a-1
would be.
@riking said:```asm
; in - al
; out - cl
; trash - eax && 0xFFFFFF00, ebx, ecx && 0xFFFFFF00
mov bl, al
xor eax, eax
mov al, bl
bsr ebx, eax # Bit scan reverse - find index of highest 1 bit
inc ebx # ebx++
mov ecx, $1 # ecx = 1
shl ecx, ebx # ecx = 1 << ebx
dec ecx # ecx = (1 << ebx) - 1
xor ecx, eax # ecx ^= inputI've got a critical chain 5 instructions long ( ͡° ͜ʖ ͡°)</blockquote> Since you can't `bsr` an R8 and Monarch will whine about how he specified an 8-bit parameter, FTFY to be 8-bit clean. Of course, Monarch will also whine about the `inc`, `dec`, `mov/imm32`, and `shl` as "math", "math", "control flow" and "not what I meant by bitwise operation"...
-
Hm, just realized it also fails for inputs of 0, but that would require a conditional branch to fix.
-
Someone on IRC did it better than I could.
<phire> smear is clever <phire> shame there isn't a smear instruction <phire> well, it's impossible to do it without touching every single bit ... <phire> optimised smear: <phire> a = x | x >> 1 <phire> b = a | a >> 2 <phire> c = b | b >> 4 <phire> x ^ c <phire> 10 instructions long
-
<phire> great thing about your method is that it works upto 32 bits * STalKer-X has quit (Ping timeout: 256 seconds) <phire> but if you benchmarked them, mine would probally be equally as fast with 8bit inputs (bsr has a 3 cycle latency) <phire> na, your one would be faster <phire> mov ecx, 1 can be executed in parallel
-
Anything over 32 tends to be difficult to address with an int as a bitmask. I've used longs (actually BIGINT as it was in SQL) for up to 64 flags before
uint64_t
wants to say hi?
-
int x : 1;
wants to say hi?As an added bonus, you can have any number of flags and they can have any power of 2 number of states.
-
How do you flip 0b1100 to 0b0011 only using bitwise operation.
0b1100 ^ 0b1111 = 0b0011
or I have completely misunderstood this.
-
Alright then, Go-daddy, what size is
int
in Go? Is it always 64 bits or does it magically change size to suit your needs as the program develops?
-
In Go,
int
is either 32 or 64 bits depending on platform. If you need one of those specifically, you can useint64
orint32
.
-
I see. How about unsigned integers?
Bitfields in C are a nice idea in theory, but generally more cause more problems than they solve...
-
There's
uint
which is guaranteed to be the same size asint
,uintptr
which is guaranteed to be the same size as a pointer (see also:unsafe
), and thenuint8
(aliased asbyte
),uint16
,uint32
, anduint64
.
-
0b1100 XOR 0b1111
Or do you not consider that to be bitwise?
0b1100 ^ 0b1111 = 0b0011 or I have completely misunderstood this.
partial solution it does not work on any given 8bit.
Since you can't bsr an R8 and Monarch will whine about how he specified an 8-bit parameter, FTFY to be 8-bit clean. Of course, Monarch will also whine about the inc, dec, mov/imm32, and shl as "math", "math", "control flow" and "not what I meant by bitwise operation"...
The guideline were to seek a solution that could work on high level languages that provide bitwise operations. The smear technique(superjer) works even in JavaScript.
any other creative solutions are welcomed as well, even if they have some math or implied control flow etc.
whaa
This should do it.
x ^ (x | x>>1 | x>>2 | x>>3 | x>>4 | x>>5 | x>>6 | x>>7)
I'll call it the "smear" technique.
congrats. here have some smeared fireworks
-
partial solution it does not work on any given 8bit.
Wait, what? 0b1100 and 0b1100 are 4bit numbers?!
-
Wait, what? 0b00001100 and 0b00001100 are 4bit numbers?!
they can be represented with 4 bit but can be contained in 8bit on the memory.
and that is what I mean't ;)
-
You want an operation that takes an arbitrary 8bit number, splits it into two 4bit numbers, reverses the bits in the 4bit numbers and sticks them together again?
-
You want an operation that takes an arbitrary 8bit number, splits it into two 4bit numbers, reverses the bits in the 4bit numbers and sticks them together again?
For any given number up to 8bits (for convenience)
flip (~ / NOT) on each bit from the most significant bit that is on, to the least significant bit.//V MSB that is on V 0b10000000 => 0b01111111 (0b1111111) V 0b00010010 => 0b00001101 (0b1101) V 0b00000011 => 0b00000000 (0b0)
see the solution by @superjer
-
quick quiz
How do you flip 0b1100 to 0b0011 only using bitwise operation.
Another example correct 0b10101 => 0b01010 wrong 0b10101 => 0b11101010
1.solution should work on any 8bit number.2. no control flow
is it possible if yes how?
Assert a 5-bit word. Duh.
-
Pure bit wise logic operations (i.e. NOT, AND, OR, XOR etc) are transitive w.r.t. circular rotation of the arguments (i.e. ROT(x) * ROT(y) == ROT(x*y)).
This problem does not have that property, so to solve it you'll have to use something that is not a pure bit-wise operation (e.g. bit-shifting).
-
For any given number up to 8bits (for convenience)
flip (~ / NOT) on each bit from the most significant bit that is on, to the least significant bit.//V MSB that is on V 0b10000000 => 0b01111111 (0b1111111) V 0b00010010 => 0b00001101 (0b1101) V 0b00000011 => 0b00000000 (0b0)
see the solution by @superjer
Your initial description was not this clear.
-10 forumpointzzz
-
-
Not enough zs; minimum of three required
-5 forumpointzzz
ERROR: INSUFFICIENT PERMISSIONS. OPERATION ABORTED.
-
This post is deleted!
-
congrats. here have some smeared fireworks
Thanks.
Is my answer really as good as it gets? I figured there would be some clever trick to do it without 7 shifts and 7 ors.