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...



  • @TheCPUWizard said:

    Bit Masked flags have their place. Unable to just the WTFffyness without the actual code...

    I agree with the first sentence. However, this ...

    @algorythmics said:

    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.



  • @HardwareGeek said:

    I agree with the first sentence. However, this ...

    @algorythmics said:

    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....


  • FoxDev

    @algorythmics said:

    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?


  • FoxDev

    …oh for fuck's sake… that's two days in a row I whooshed badly 😊


  • Java Dev

    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....


  • Java Dev

    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 or field |= DEFINED_FLAG to be so complex they need functions/defines.


  • kills Dumbledore

    @RaceProUK said:

    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



  • @TheCPUWizard said:

    Bit Masked flags have their place. Unable to just the WTFffyness without the actual code...

    Hmm, trying to determine what was meant. Some options:

    @TheCPUWizard said:

    Bit Masked flags have their place. Unable to justify the WTFffyness without the actual code...

    @TheCPUWizard said:

    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
    wrong 0b10101 => 0b11101010

    1.solution should work on any 8bit number.
    2. no control flow

    is 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.


  • Java Dev

    My point exactly. The only thing that should be #defined is the name of the flag, because 0x01, 0x02, 0x04, etc… are magic numbers.


  • Java Dev

    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.



  • @Monarch said:

    ###quick quiz

    How do you flip 0b1100 to 0b0011 only using bitwise operation.

    Another example
    <ins>correct</ins> 0b10101 => 0b01010
    <del>wrong</del> 0b10101 => 0b11101010

    1.solution should work on any 8bit number.
    2. no control flow

    is 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!



  • @PleegWat said:

    Flip bits only up to and including the most significant set bit?

    yes that.

    @abarker said:

    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

    Proof: http://play.golang.org/p/mpvDxnlGv6



  • 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.


  • Java Dev

    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



  • @Monarch said:

    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 ^= input

    I've got a critical chain 5 instructions long ( ͡° ͜ʖ ͡°)


  • FoxDev

    XOR with -1?



  • @accalia said:

    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 ^= input

    I'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
    


  • @Jaloopa said:

    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.



  • @Monarch said:

    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?



  • That was actually C.

    In Go, int is either 32 or 64 bits depending on platform. If you need one of those specifically, you can use int64 or int32.



  • 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 as int, uintptr which is guaranteed to be the same size as a pointer (see also: unsafe), and then uint8 (aliased as byte), uint16, uint32, and uint64.



  • @abarker said:

    0b1100 XOR 0b1111

    Or do you not consider that to be bitwise?

    @tar said:

    0b1100 ^ 0b1111 = 0b0011 or I have completely misunderstood this.

    partial solution it does not work on any given 8bit.


    @TwelveBaud said:

    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 🍼


    @superjer said:

    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



  • @Monarch said:

    partial solution it does not work on any given 8bit.

    Wait, what? 0b1100 and 0b1100 are 4bit numbers?!



  • @tar said:

    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?



  • @tar said:

    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



  • @Monarch said:

    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).



  • @Monarch said:

    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 =&gt; 0b01111111  (0b1111111)
    
         V
    0b00010010 =&gt; 0b00001101  (0b1101)
    
            V
    0b00000011 =&gt; 0b00000000  (0b0)
    

    see the solution by @superjer

    Your initial description was not this clear.

    -10 forumpointzzz


  • FoxDev

    @abarker said:

    -10 forumpointz

    Not enough zs; minimum of three required

    -5 forumpointzzz



  • @RaceProUK said:

    Not enough zs; minimum of three required

    -5 forumpointzzz

    ERROR: INSUFFICIENT PERMISSIONS. OPERATION ABORTED.



  • This post is deleted!


  • @Monarch said:

    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.


Log in to reply