Pretty cool lil nerd out

[markyrocks]

I've been playing around with this for a lil bit.  Not necessary mulling over the actual solving of the problem but the reversing of a series of bits... like its got my ocd kicking in.  I know that it has to be possible algorithmically using some combination of bitwise operations, that doesn't involve a loop.... loops are BAD!! BAD LOOP NO.  I just can't wrap my brain around it.  Anyways its just for fun.  The point of this is to check to see if a series of bits are a palindrome.  so if you only had 8 bits it would need to look like 0001 1000 etc.  An earlier version I had them all being checked individually but i was trying to come up with something a little cleaner...  If you got any ideas hit me up.  Its not that big of a deal bc its just some random thing someone of fb was asking for help with.    Like shouldn't I be able to make the computer just read it backwards? like wtf. change the encoding or something.  

void reversebyte(byte* p) {

    byte b = 0;;

    for (int i = 0; i < 8; i++) {
        if(*p & (1 << i)){
            b |= 1 << 7 - i;
        }
    }
    *p = b;

}


int main() {
    
    int a = 1;
    byte b[4]{};

    while (a < 100000000) {

        *(int*)&b = a;

        reversebyte(&b[0]);
        reversebyte(&b[1]);

        if (b[0] == b[3] && b[1] == b[2]) {
            cout << "good result : a = " << a << "\n";
        }
        a++;
    }

}

 

on the topic of reversing a series of bit.  I can get it to work sometimes because of my bits are 0101  bitwise ~ is a good reverse which would be 1010  

something like 1101 ~ is 0010  so no good.  

[Werty]

How about using a look-up table with all the 256 different bytes in an array representet as bits, would probably be faster also, as you wouldnt need to calculate anything.

 

[markyrocks]

28 minutes ago, Werty said:

How about using a look-up table with all the 256 different bytes in an array representet as bits, would probably be faster also, as you wouldnt need to calculate anything.

 

Hmmmmm ... wouldn't even be 256 they'd only need to be a map of 128 that was reflective of whatever the mirror was.  Not to mention that would scale up very well.   I'm not usually a fan of the database type approach but being so small....ya I like it.  Again this is just for fun but that's....wait I have something coming I think.   An algorithm maybe looming.. I'll report back. 

[markyrocks]

So I been chewing this over on my lunch break and the last exchange got me thinking.  The 128 number wasn't correct.   The byte can easily be broken into 2 halves that  each half only has 16 different combinations.... of those 16 four of them {0,6,9,15} already reflect themselves.   So that leaves 6 mapped pairs?... This is the kinda efficiency I'm talking about.   Yeah!!  Let me get out my can of loop be gone.  I still believe that there's an algorithm in here.  I'm just zeroing in on it.  

2 of the pairs can simply be flipped.  So now we have 2 groups those that can be flipped and those that cant..... 

Edited January 25, 2022 by markyrocks

[funkey]

Bit Twiddling Hacks (stanford.edu)

[AndyG]

On 1/25/2022 at 6:16 AM, markyrocks said:

that doesn't involve a loop.... loops are BAD!!

In Assembler, "Loop unrolling" is (should be) very common to solve the "problem" with loops.

So if you don´t want to use some of the Bit Twiddling Hacks mentioned by funkey, unroll your "bad" loop. 

Functions to reverse bits in Byte, Word, Dword

Func _BitreverseByte($byte)          ;reverses bits in the lower 8 bits of $byte
            Return BitOR( _                  ;add all shifted bits together
                    BitShift(BitAND($byte, 0x01), -7), _ ;Bit 0 to bit 7
                    BitShift(BitAND($byte, 0x02), -5), _ ;Bit 1 to bit 6
                    BitShift(BitAND($byte, 0x04), -3), _ ;Bit 2 to bit 5
                    BitShift(BitAND($byte, 0x08), -1), _ ;Bit 3 to bit 4
                    BitShift(BitAND($byte, 0x10), 1), _ ;Bit 4 to bit 3
                    BitShift(BitAND($byte, 0x20), 3), _ ;Bit 5 to bit 2
                    BitShift(BitAND($byte, 0x40), 5), _ ;Bit 6 to bit 1
                    BitShift(BitAND($byte, 0x80), 7)) ;Bit 7 to bit 0
        EndFunc                              ;==>_BitreverseByte


        Func _bitreverseWord($word)          ;reverses bits in the lower 16 bits of $byte
            Return BitOR( _
                    _BitreverseByte(BitShift($word, 8)), _ ;reverses upper 8 bits and shift to lower 8 bits
                    BitShift(_BitreverseByte($word), -8)) ;reverses lower 8 bits and shift to higher 8 Bits
        EndFunc                              ;==>_bitreverseWord


        Func _bitreverseDword($dword)
            Return BitOR( _
                    _BitreverseByte(BitShift($dword, 24)), _ ;reverses upper 8 bits and shift to lower 8 bits
                    BitShift(_BitreverseByte(BitShift($dword, 16)), -8), _ ;
                    BitShift(_BitreverseByte(BitShift($dword, 08)), -16), _ ;
                    BitShift(_BitreverseByte(BitShift($dword, 00)), -24)) ;reverses lower 8 bits and shift to higher 8 Bits
        EndFunc                              ;==>_bitreverseDword

 

But i think these functions are not relating to 

On 1/25/2022 at 6:16 AM, markyrocks said:

The point of this is to check to see if a series of bits are a palindrome.

For example 111, 101, 100111001, are palindromes which can not be calculated with functions having a restriction to the length of byte/word/dword.

The question is, are leading zeroes (up to a given length of the whole "bitstring") also allowed, so that 001100 or 0111011101110 or 000010000 are palindromes too?

If only palindromes are allowed with a leading 1, only odd numbers are in the value area .

expandcollapse popup

Global $a_[256], $b_[256], $c_[11111112]        ;only to show the binarystring
_DecToBin_Startup()                             ;only to show the binarystring


For $i = 1 To 50050 step 2
    If _isbitpalindrome($i) Then ConsoleWrite($i & "    " & _DecToBin($i) & @CRLF)
Next





Func _isbitpalindrome($uint)                    ;returns 1 if uint is bitpalindrome
    Local $reversed = 0
    Local $i = $uint
    While $i > 0                                ;until all bits are shifted
        $reversed = BitOR(BitShift($reversed, -1), BitAND($i, 1)) ;shift LSB of $i into $reversed
        $i = BitShift($i, 1)                    ;next bit of $i
    WEnd
    Return ($reversed = $uint) ? 1 : 0
EndFunc                                         ;==>_isbitpalindrome





;functions by mars
;https://autoit.de/thread/28809-suche-schnelle-funktion-zum-umrechnen-ins-dual-oder-hexadezimalsystem/?pageNo=1
Func _BinToDec($bin)
    Local $dec = 0, $array = StringSplit($bin, "")
    For $i = $array[0] To 1 Step -1
        If $array[$i] = "1" Then $dec += 2 ^ ($array[0] - $i)
    Next
    Return $dec
EndFunc                                         ;==>_BinToDec

; <Func>--------------------------------------------------|
; Ermittelt eine Dualzahl (0101) aus einer Dezimalzahl |
; Die Dezimalzahl muss kleiner als 2^31 sein |
; --------------------------------------------------------|
Func _DecToBin($d)
    Return $d < 256 ? $a_[$d] : $d < 65536 ? $a_[$d / 256] & $b_[BitAND($d, 255)] : $d < 16777216 ? $a_[$d / 65536] & $b_[BitAND($d / 256, 255)] & $b_[BitAND($d, 255)] : $a_[BitShift($d, 24)] & $b_[BitAND($d / 65536, 255)] & $b_[BitAND($d / 256, 255)] & $b_[BitAND($d, 255)]
EndFunc                                         ;==>_DecToBin



; <Func>--------------------------------------------------|
; Initialisiert die DecToBin UDF |
; --------------------------------------------------------|
Func _DecToBin_Startup()
    Local $t = DllStructCreate('char[64]'), $p = _
            DllStructGetPtr($t), $hDll = DllOpen('msvcrt.dll')
    For $i = 0 To 255 Step 1
        DllCall($hDll, 'ptr:cdecl', '_i64toa', 'int64', _
                $i, 'ptr', $p, 'int', 2)
        $a_[$i] = DllStructGetData($t, 1)
        $b_[$i] = StringRight('0000000' & $a_[$i], 8)
        $c_[$a_[$i]] = $i
    Next
    DllClose($hDll)
EndFunc                                         ;==>_DecToBin_Startup

 

//EDIT

got faster function _isbitpalindrome() and from the "old" one _reversebits()

Func _isbitpalindrome($uint)              ;returns 1 if uint is bitpalindrome
    Local $msb, $lsb
    For $msb = 31 To 0 Step -1            ;get position of msb from 31 to 0
        If BitAND($uint, BitShift(1, -$msb)) Then ExitLoop
    Next
    While $lsb < $msb                     ;compare 2 bits
        If (BitAND($uint, BitShift(1, -$lsb)) ? 1 : 0) <> (BitAND($uint, BitShift(1, -$msb)) ? 1 : 0) Then Return 0 ;the 2 bits are not equal
        ;bits are equal, compare next 2 bits
        $lsb = $lsb + 1                   ;bitposition
        $msb = $msb - 1                   ;bitposition
    WEnd
    Return 1
EndFunc                                   ;==>_isbitpalindrome


Func _reversebits($uint)                  ;reverses the bits of a given uint
    Local $reversed = 0
    While $uint > 0                       ;until all bits are shifted
        $reversed = BitOR(BitShift($reversed, -1), BitAND($uint, 1)) ;shift LSB of $uint into $reversed
        $uint = BitShift($uint, 1)        ;next bit of $uint
    WEnd
    Return $reversed
EndFunc                                   ;==>_reversebits

 

Edited January 27, 2022 by AndyG