TheBackShed.com

Forum Index : Microcontroller and PC projects : 4 Bit reorder

Author

Message

jman

Guru

Joined: 12/06/2011
Location: New Zealand
Posts: 711

Posted: 12:14am 03 Jul 2013

Copy link to clipboard

Print this post

Hi

I working a little project that I need to reorder a 4bit nibble
for example (1-4 2-3 3-2 4-1)
In Out
0001 1000
0010 0100
0011 1100
0100 0010
1000 0001 etc...

I am sure you smart people that hang around here have
a simple way of doing this ?

Thanks
John

Edited by jman 2013-07-04

kiiid

Guru

Joined: 11/05/2013
Location: United Kingdom
Posts: 671

Posted: 12:54am 03 Jul 2013

Copy link to clipboard

Print this post

I am sure there is a mathematical way, but for 4-bit numbers, that's 16 values only. A lookup table would do the job easily

http://rittle.org

--------------

MOBI
Guru

Joined: 02/12/2012
Location: Australia
Posts: 819

Posted: 02:03am 03 Jul 2013

Copy link to clipboard

Print this post

What platform/language are you using e.g. PIC, AVR, PC? Assembly, C, VB??

David M.

jman

Guru

Joined: 12/06/2011
Location: New Zealand
Posts: 711

Posted: 02:04am 03 Jul 2013

Copy link to clipboard

Print this post

Maximite Basic 4.3

John

ajkw
Senior Member

Joined: 29/06/2011
Location: Australia
Posts: 290

Posted: 02:07am 03 Jul 2013

Copy link to clipboard

Print this post

byte = 19566 ' sample 0100110001101110

for i = 15 to 0 step -1
newbyte = newbyte + ((2^(15-i)) * ((byte AND (2 ^ i)) > 0))
next i

print newbyte ' Should return 30258 being 0111011000110010

2 little changes required for 4 bits instead of 16 as in the example.

From Topic
http://www.thebackshed.com/forum/forum_posts.asp?TID=5420&KW =swap+bits&TPN=3

Sample code only, make sure you do your own error testing and that it suits your purpose!

Dylan
Regular Member

Joined: 17/06/2013
Location: Netherlands
Posts: 81

Posted: 05:46am 03 Jul 2013

Copy link to clipboard

Print this post

I agree with Kon that a look-up table is the way to go.

ajkw has a workable solution, but given that Maximite has 32-bit float arithmetic, performing 8 (let alone 32) ^ operations might not be what you want.

r = (b AND 1) * 8 + (b AND 2) * 4 + (b AND 4) * 2 + (b AND 8) * 1 ' is versatile, 11 ops.

Divide and conquer (a la http://stackoverflow.com/questions/9144800/c-reverse-bits-in -unsigned-integer):
x = (x\2 AND 5) + (x AND 5)*2 ' 5 ops;
x = (x\4 AND 3) + (x AND 3)*4 ' saves an operation, but adds an assignment.

RTFineM: http://geoffg.net/Downloads/Maximite/MMBasic%20Language%20Ma nual.pdf (page 14)

Function Bit(nbr, bit)
If nbr < 0 or bits < 0 THEN ERROR "Invalid argument"
Bit = (nbr\(2^bit)) AND 1
End Function

x = Bit(x, 3) + Bit(x, 2) * 2 + Bit(x, 1) * 4 + Bit(x, 0) * 8 ' or vice versa!

Mathematical way:
http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT#Data_r eordering.2C_bit_reversal.2C_and_in-place_algorithms
http://en.wikipedia.org/wiki/Bit-reversal_permutation
Both of which are shotguns for gnats. ;)

MicroBlocks

Guru

Joined: 12/05/2012
Location: Thailand
Posts: 2209

Posted: 06:42am 03 Jul 2013

Copy link to clipboard

Print this post

I also prefer a table. They are quick, and easy to understand and maintain.
Al those fancy calculations are just mental exercises, they don't gain much in an interpreted language and most are not even faster when used in assembly.
If someone else looks at your code, he would probably think, what a show off. Just get it done.

And there are so many ways to get it done, even with lookup tables.
You can even make it with an on nbr goto statement. Oh the horror.

I prefer to look at a piece of code and see what it is doing without having to step through it line by line with a calculator and check for open and close braces to get the order. Double horror.

Just make a table of numbers, fill it one by one when there are not much numbers or use a for next loop to read DATA. If it is a big lookup table store it in a file.
It scales very well and you can even use it in many other instances where it is not only a reversal of bits.
After that it is just B = Translate(A)

Edited by TZAdvantage 2013-07-04

Microblocks. Build with logic.

Dylan
Regular Member

Joined: 17/06/2013
Location: Netherlands
Posts: 81

Posted: 07:13am 03 Jul 2013

Copy link to clipboard

Print this post

XLAT (http://en.wikipedia.org/wiki/X86_instruction_listings)

ajkw
Senior Member

Joined: 29/06/2011
Location: Australia
Posts: 290

Posted: 05:26pm 14 Jul 2013

Copy link to clipboard

Print this post

Just in case someone searches the forum and finds this thread

I liked the look of this

Quote r = (b AND 1) * 8 + (b AND 2) * 4 + (b AND 4) * 2 + (b AND 8) * 1 ' is versatile, 11 ops.

but it does not work.

eg: 2 and 2 = 2 not 1. (2 and 2) * 4 = 8 (not 4 like it needs to be)

so a little change to

r = ((b AND 1)>0) * 8 + ((b AND 2)>0) * 4 + ((b AND 4)>0) * 2 + ((b AND 8)>0) * 1

does work.

No ^ ops, no for/next loops, 1 line, but has braces and will get cumbersome for 8 let alone 16 or 32 bits.

I wonder how John got on??

MicroBlocks

Guru

Joined: 12/05/2012
Location: Thailand
Posts: 2209

Posted: 08:33pm 14 Jul 2013

Copy link to clipboard

Print this post

I like oneliners for the sport of it, and being unclear is mandatory. :)
This one reverses a nibble. :)
Is this the shortest?
It does only 5 operations so it should also be fast.
[code]
r = ASC(MID$("084<2:6>195=3;7?",(b AND 15) + 1,1)) AND 15
[/code]

it is essentially only a lookup table, the use of mid$ is specific for basic as it does not have a byte array.

This can easily be changed to 8 bits.
It would be easier to define the lookup string separate.
[code]
l$ = "................" 'fill with characters that translate the input character
r = ASC(MID$(l$,(b AND 255) + 1,1))
[/code]
Edited by TZAdvantage 2013-07-16

Microblocks. Build with logic.

JohnS
Guru

Joined: 18/11/2011
Location: United Kingdom
Posts: 3678

Posted: 09:42pm 14 Jul 2013

Copy link to clipboard

Print this post

I like the idea of using MID$

Arguably a more readable version would be to use printable characters people generally know, though it's complicated by wanting to keep the code short.

ASC("@") is 64 (binary 0100 0000), so lots of low zero bits, and from there on we have "ABCDEFG" (etc).

I think this gives
new = ASC(MID$("@HDLBJFNAIEMCKGO", nibble + 1, 1) AND 15

As a quick check, we're reordering the numbers 0 to 15 so there should be 16 consecutive chars of the character set but shuffled, which there are ("@ABCDEFGHIKLMNO").

John

MicroBlocks

Guru

Joined: 12/05/2012
Location: Thailand
Posts: 2209

Posted: 10:16pm 14 Jul 2013

Copy link to clipboard

Print this post

I like the more readable range of "@ABCDEFGHIKLMNO"
I picked the range i used because it has the 0123456789 in it so that at least 10 of the 16 will have the right visible value.
1 becomes 8, 2 becomes 4, 4 becomes 2 etc.
Maybe
@HDLBJFNAIEMCKGO
mixed with
084<2:6>195=3;7?
becomes
084L2J6N195M3K7?

It adds to the obscurity and is a better puzzle for ones trying to figure it out.

Microblocks. Build with logic.

Print this page

To reply to this topic, you need to log in.