Bit Shifting

Bare metal programming in PureBasic, for experienced users
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Bit Shifting

Post by interfind »

How can i shift the first left single Bit in rax on Bit to Left

eax = 000000100011111 --> 00000100011111 --> 0000100011111 --> 000100011111 an so on.

If rax = 10000000011111 then the next 1-Bit goes to Left --> 0000000001101111 an so on.

This should done for all Bits set to 1.

The result an the End must be 1111110000000000.

What is the fastest way to do it?

I know i can get the first left Bit in rax with BSR rcx, rax

I hope i have explain it well :)
juergenkulow
Enthusiast
Enthusiast
Posts: 544
Joined: Wed Sep 25, 2019 10:18 am

Re: Bit Shifting

Post by juergenkulow »

Code: Select all

;BSR rcx,rax
Debug Hex( %000000100011111)
Debug Hex(  %00000100011111)
Debug Hex(   %0000100011111) 
Debug Hex(    %000100011111)

Debug Hex(  %10000000011111)
Debug Hex(%0000000001101111)

Debug Hex(%1111110000000000)
;                          32109876543210
Define regrcx.q, regrax.q=%10000000011111
DisableDebugger:EnableASM
MOV rax,[v_regrax]
BSR rcx,rax
MOV [v_regrcx],rcx
EnableDebugger
Debug regrcx
; 11F
; 11F
; 11F
; 11F
; 201F
; 6F
; FC00
; 13
BSR — Bit Scan Reverse
What do you want to achieve with BSR?
Please ask your questions, because switch on the cognition apparatus decides on the only known life in the universe.Wersten :DDüsseldorf NRW Germany Europe Earth Solar System Flake Bubble Orionarm
Milky Way Local_Group Virgo Supercluster Laniakea Universe
User avatar
NicTheQuick
Addict
Addict
Posts: 1224
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Bit Shifting

Post by NicTheQuick »

interfind wrote: Tue Feb 07, 2023 2:54 pm How can i shift the first left single Bit in rax on Bit to Left

eax = 000000100011111 --> 00000100011111 --> 0000100011111 --> 000100011111 an so on.
That's all the same numbers.
If rax = 10000000011111 then the next 1-Bit goes to Left --> 0000000001101111 an so on.

This should done for all Bits set to 1.

The result an the End must be 1111110000000000.
I also did not understand what you mean with that.
I hope i have explain it well :)
Unfortunately not.
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
User avatar
NicTheQuick
Addict
Addict
Posts: 1224
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Bit Shifting

Post by NicTheQuick »

I can only imagine you mean something like this:

Code: Select all

EnableExplicit

Procedure highestBit(i.i)
    i | (i >>  1)
    i | (i >>  2)
    i | (i >>  4)
    i | (i >>  8)
    i | (i >> 16)
    ProcedureReturn i & ~(i >> 1)
EndProcedure

Define a = %100011111
Define hb

While a
	Debug RSet(Bin(a), 32, "0")
	hb = highestBit(a)
	a = ((hb << 1) | (a & (hb -1))) & ($ffffffff)
Wend
But there are also ASM instructions which can return the highest bit in O(1) instead of writing an extra procedure for that. I just don't know how to use them.
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post by interfind »

Your Code is good, but all 1 Bits from the right side
must go to the left side an stay here at the end
of the Procedur.

I like do set the max left Position by myself-

00001111
00010111
00100111
01000111
10000111
00011011
00101011
01001011
10001011
00110011
01010011
10010011
01100011
10100011
11000011
00011101

Final should be

11110000
User avatar
NicTheQuick
Addict
Addict
Posts: 1224
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Bit Shifting

Post by NicTheQuick »

That needs a lot more logic then or I did not get the pattern behind it.

Why do you need that? What's the reason?
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
User avatar
NicTheQuick
Addict
Addict
Posts: 1224
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Bit Shifting

Post by NicTheQuick »

Does the sequence always start with n · zeros and m · ones concatenated with another and stops in m · ones and n · zeros, so the whole thing reversed in principle? And in between you want to see all possible values you can create using these bits but it has to be in that specific sequence?
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
User avatar
NicTheQuick
Addict
Addict
Posts: 1224
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Bit Shifting

Post by NicTheQuick »

I think what you are looking for is a function which gives you the next lexicographic permutation of a number.
Here is an explanation: https://youtu.be/ZRNO-ewsNcQ?t=1004
And here a code: https://www.geeksforgeeks.org/lexicogra ... on-in-cpp/
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post by interfind »

NicTheQuick wrote: Tue Feb 07, 2023 5:53 pm Does the sequence always start with n · zeros and m · ones concatenated with another and stops in m · ones and n · zeros, so the whole thing reversed in principle? And in between you want to see all possible values you can create using these bits but it has to be in that specific sequence?
Yes , this should be what i'm trying. in exactly that sequence in Assembler.
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post by interfind »

NicTheQuick wrote: Tue Feb 07, 2023 6:18 pm I think what you are looking for is a function which gives you the next lexicographic permutation of a number.
Here is an explanation: https://youtu.be/ZRNO-ewsNcQ?t=1004
And here a code: https://www.geeksforgeeks.org/lexicogra ... on-in-cpp/
Yes, but not in lexicographic rather in the sequence i was showing in my Post's.
User avatar
NicTheQuick
Addict
Addict
Posts: 1224
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Bit Shifting

Post by NicTheQuick »

interfind wrote: Tue Feb 07, 2023 6:31 pm
NicTheQuick wrote: Tue Feb 07, 2023 5:53 pm Does the sequence always start with n · zeros and m · ones concatenated with another and stops in m · ones and n · zeros, so the whole thing reversed in principle? And in between you want to see all possible values you can create using these bits but it has to be in that specific sequence?
Yes , this should be what i'm trying. in exactly that sequence in Assembler.
Wait. Why in Assembler? Do you not trust compiler optimizations? This seems unnecessary to me.
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post by interfind »

NicTheQuick wrote: Tue Feb 07, 2023 6:45 pm
interfind wrote: Tue Feb 07, 2023 6:31 pm
NicTheQuick wrote: Tue Feb 07, 2023 5:53 pm Does the sequence always start with n · zeros and m · ones concatenated with another and stops in m · ones and n · zeros, so the whole thing reversed in principle? And in between you want to see all possible values you can create using these bits but it has to be in that specific sequence?
Yes , this should be what i'm trying. in exactly that sequence in Assembler.
Wait. Why in Assembler? Do you not trust compiler optimizations? This seems unnecessary to me.
For Speeed. When the sequence goes over 64Bit , this can take more days to finish.
User avatar
NicTheQuick
Addict
Addict
Posts: 1224
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Bit Shifting

Post by NicTheQuick »

Up to how many bits should it work?
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post by interfind »

NicTheQuick wrote: Tue Feb 07, 2023 7:12 pm Up to how many bits should it work?

Up to the 50's Bit Position and up to N (1-26) Bit's set to 1
User avatar
mk-soft
Always Here
Always Here
Posts: 5335
Joined: Fri May 12, 2006 6:51 pm
Location: Germany

Re: Bit Shifting

Post by mk-soft »

Where is bit 0 for you?
Bit 0 is always on the far right.
My Projects ThreadToGUI / OOP-BaseClass / EventDesigner V3
PB v3.30 / v5.75 - OS Mac Mini OSX 10.xx - VM Window Pro / Linux Ubuntu
Downloads on my Webspace / OneDrive
Post Reply