Announcement

Collapse
No announcement yet.

Find Lowest Set Bit

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Find Lowest Set Bit

    Been doing a bit of Boolean Algebra recently (using bit flags/enumerations) and I just came across a neat little "bit twiddle" that may be of use to someone else.
    To detemine the lowest set bit in an integer type variable just AND the number with it's negative
    (it works for unsigned integers too even though theoretically you can't have the negative of an unsigned integer.)
    '
    Code:
    #COMPILE EXE
    #DIM ALL
    FUNCTION PBMAIN() AS LONG
        LOCAL x AS DWORD
        LOCAL s AS STRING
        FOR x = 1 TO 33
            s+= STR$(x) & STR$(x AND -x) & $LF
        NEXT
        ? s
    #IF %DEF(%PB_CC32)
        WAITKEY$
    #ENDIF
    END FUNCTION
    '
    ---------------------------
    PowerBASIC
    ---------------------------
    1 1
    2 2
    3 1
    4 4
    5 1
    6 2
    7 1
    8 8
    9 1
    10 2
    11 1
    12 4
    13 1
    14 2
    15 1
    16 16
    17 1
    18 2
    19 1
    20 4
    21 1
    22 2
    23 1
    24 8
    25 1
    26 2
    27 1
    28 4
    29 1
    30 2
    31 1
    32 32
    33 1

    ---------------------------
    OK
    ---------------------------





  • #2
    'For the curious - same in assembly.
    '(though hard to beat Stewart's method unless already doing assembly.)
    '
    Code:
    #compile exe
    #dim all
    
    function pbmain () as long
      local NUT as long 'Number Under Test (can also be dword, integer or word)
      local BitNum as long
      NUT = 88 'is &b1011000
      ! PUSH EBX  'need for PUSH/POP depends on where imbedding  
      ! BSF EBX, NUT 'Bit Scan Forward ((or BX for 16 bit NUT))
      ! MOV BitNum, EBX
      ! POP EBX
      ? str$(BitNum) 'result should be "3"
    end function
    'There is also BSR (Bit Scan Reverse for finding most significant set bit
    '
    'Cheers,
    Dale

    Comment


    • #3
      ! PUSH EBX 'need for PUSH/POP depends on where imbedding
      If you use EAX as the register, instead of EBX, then there is no need to push/pop it as EAX, ECX and EDX are always available for you to use and don't need to be preserved.

      Comment


      • #4
        Originally posted by Dale Yarker View Post
        'For the curious - same in assembly.
        Slightly different. Your routine returns the bit number(0,1,2...), mine returns the bit value(1,2,4...)

        Comment


        • #5
          Without writing a program to test it, does anyone want to state what
          Code:
          x AND -(x AND 1)
          returns?

          If you've got that one, how aboout
          Code:
          x AND NOT(-(x AND 1))

          Comment


          • #6
            Love the logic

            Wouldn't it be faster (and messier) just to use the bit function up to 33 times?

            I have not written the code or done a time test!
            [I]I made a coding error once - but fortunately I fixed it before anyone noticed[/I]
            Kerry Farmer

            Comment


            • #7
              Originally posted by Kerry Farmer View Post
              Love the logic

              Wouldn't it be faster (and messier) just to use the bit function up to 33 times?
              But what if it's a WORD or QUAD?
              I thought about another generic bit twiddle to determine the highest set bit, but ran into the same issue of deciding "on the fly" how many bits we are working with (Any suggestion on how to do that is welcome )

              Comment


              • #8
                x AND -(x AND 1)
                I think it will find all prime numbers and a few non prime besides.
                Rod
                In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

                Comment


                • #9
                  finding the highest set bit
                  Code:
                  LOCAL j AS QUAD
                      LOCAL k AS LONG
                      j=339988822221
                      k=INSTR(BIN$(j,64),"1")
                      ? STR$(k)
                  Rod
                  In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

                  Comment


                  • #10
                    Originally posted by Stuart McLachlan View Post

                    but ran into the same issue of deciding "on the fly" how many bits we are working with (Any suggestion on how to do that is welcome )
                    Assign the value to a QUAD then you know there are 64 bits to deal with every time.

                    Comment


                    • #11
                      Yep,, based on Rod's code,
                      Code:
                      2 ^ (64 - INSTR(BIN$(x,64),"1"))
                      returns the value of the highest bit it if x <> 0
                      (But it's not "bit twiddling" )

                      Comment


                      • #12
                        Originally posted by Paul Dixon View Post

                        Assign the value to a QUAD then you know there are 64 bits to deal with every time.
                        Good idea. Now to find the Boolean expression that returns the highest set bit.....

                        Comment


                        • #13
                          (But it's not "bit twiddling" )
                          Not that I'm in agreement with this, but it is a tad humourous, IMO. And you're right, what we did is not bit twiddling,
                          bit twiddling [very common] 1. (pejorative) An exercise in tuning (see tune) in which incredible amounts of time and effort go to produce little noticeable improvement, often with the result that the code becomes incomprehensible. 2. Aimless small modification to a program, esp. for some pointless goal.
                          From: https://www.definitions.net/definition/bit%20twiddling
                          Rod
                          In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

                          Comment


                          • #14
                            Originally posted by Rodney Hicks View Post
                            Not that I'm in agreement with this, but it is a tad humourous, IMO. And you're right, what we did is not bit twiddling,

                            From: https://www.definitions.net/definition/bit%20twiddling
                            Alternatively, good old Wikipedia:

                            Bit twiddling and bit bashing are often used interchangeably with bit manipulation, but sometimes exclusively refer to clever or non-obvious ways or uses of bit manipulation, or tedious or challenging low-level device control data manipulation tasks.

                            The term bit twiddling dates from early computing hardware, where computer operators would make adjustments by tweaking or twiddling computer controls. As computer programming languages evolved, programmers adopted the term to mean any handling of data that involved bit-level computation.

                            Comment


                            • #15
                              While quickly looking for a nicer definition of "bit twiddling", I came across a great resource:
                              https://graphics.stanford.edu/~seander/bithacks.html
                              Bit Twiddling Hacks
                              By Sean Eron Anderson


                              Lo and behold:
                              Finding integer log base 2 of an integer (aka the position of the highest bit set)
                              The "obvious way":

                              Where x > 0
                              Bit position = FIX(LOG2(x))
                              Value of the bit = 2^FIX(LOG2(x))

                              Comment


                              • #16
                                Here is another one for your Boolean Algebra toolbox, Stuart. It simply counts the number of set bits. It does the same job as the asm popcnt, but older machines don't have that.
                                Code:
                                While k <> 0
                                  k = k And k - 1
                                  numBits += 1
                                Wend
                                where k is any integral data type.

                                I am using it to determine the Hamming weight of PRNG seeds.

                                Comment


                                • #17
                                  Originally posted by David Roberts View Post
                                  Here is another one for your Boolean Algebra toolbox, Stuart. It simply counts the number of set bits. It does the same job as the asm popcnt, but older machines don't have that.
                                  Code:
                                  While k <> 0
                                  k = k And k - 1
                                  numBits += 1
                                  Wend
                                  where k is any integral data type.

                                  I am using it to determine the Hamming weight of PRNG seeds.
                                  Yep, I also found that one in the Bit Tweaking reference above
                                  It does hve the disadvantage that it alters the value of the variable, so you need to do an assignment to a temp variable
                                  Code:
                                  tmp=x
                                  WHILE tmp > 0
                                  tmp AND= (tmp -1)
                                  INCR y
                                  WEND
                                  ? Str$(x) & " has " &  str$(y) & " bits set"

                                  Comment


                                  • #18
                                    Originally posted by Stuart McLachlan View Post
                                    Without writing a program to test it, does anyone want to state what
                                    Code:
                                    x AND -(x AND 1)
                                    returns?

                                    If you've got that one, how aboout
                                    Code:
                                    x AND NOT(-(x AND 1))
                                    No other takers? (Rod didn't quite get it)

                                    Comment


                                    • #19
                                      Code:
                                      x AND -(x AND 1)
                                      if x is odd it returns x, if x is even it returns 0

                                      Thinking on 2nd one.
                                      Dale

                                      Comment


                                      • #20
                                        2nd
                                        x XOR x is less steps
                                        Dale

                                        Comment

                                        Working...
                                        X