Go Down

Topic: Convert bitmath into regular math? (Read 1 time) previous topic - next topic

dkl65

Jun 11, 2012, 03:15 am Last Edit: Jun 11, 2012, 05:04 pm by dkl65 Reason: 1
Hello!
I was wondering if bitmath (bitshift left, bitshift right, OR, XOR, AND, NOT) and modulo can be expressed using regular math (add, subtract, multiply, divide). I know that NOT in regular math is (-x)-1. How about the other bitwise operations?

Is the symbol ` and $ ever used in Arduino? What is it used for?

Thanks!
Visit http://www.glenof.webs.com/!

Delta_G

Bitshift left and right are multiplication and division by powers of 2.


GoForSmoke

The bitmath is generally more efficient and never that I know of less so.

I find it harder to express logic in English than in Code.
Sometimes an example says more than many times as many words.

WizenedEE

In bash, the backtick (`) means "execute this and replace with stdout" but it's depreciated (the $(command) is preferred).

robtillaart

Quote
I was wondering if bitmath (bitshift left, bitshift right, OR, XOR, AND, NOT) can be expressed using regular math

I think that in theory all can be expressed in regular math but the complexity involved would explode for some operations. (Never tried / investigated disclaimer :)
I even think you need to hold state in between

the bitshifts are easy, as is the NOT, However to express an AND in normal math would include isolation of individual bits by using powers of 2 for every bit to isolate them and then multiply the bits on the same position and add the results.

for a 2 bitter the formula involved 4 divisions and 1 multiply - and that is the easiest but 1

a= 01
b= 11
c = (a/2 * b/2)*2 + (a%2 * b%2); // c = b & a

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

dkl65


a= 01
b= 11
c = (a/2 * b/2)*2 + (a%2 * b%2); // c = b & a

Is a (01) and b (11) binary intergers, or decimal intergers?

34 << 3 = 34 * 23 = 272
Visit http://www.glenof.webs.com/!

AWOL

Quote
Is a (01) and b (11) binary intergers, or decimal intergers?

"01" is an octal integer
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

dkl65

01 (octal), 0x1 (hexadecimal), 1 (decimal) and 0b1 (binary) is all the same. However, I don't know what kind of number b (11) is. If I guess wrong, the outcome will be very different.
Visit http://www.glenof.webs.com/!

AWOL

Quote
I don't know what kind of number b (11)

Quote
for a 2 bitter

There's a clue   ;)
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

dkl65

#9
Jun 11, 2012, 04:50 pm Last Edit: Jun 11, 2012, 05:03 pm by dkl65 Reason: 1
Oh! I thought that "bitter" was refering to the taste, or something harsh / bad. Instead, it means "2 bits". So the numbers must be binary! If they are binary...

(1/2 * 3/2)*2 + (1%2 * 3%2) = 2.5
3 & 1 = 1

So either robtillaart is wrong, or I am wrong. Also, % (modulo) is not regular math.
Visit http://www.glenof.webs.com/!

AWOL

#10
Jun 11, 2012, 04:57 pm Last Edit: Jun 11, 2012, 05:00 pm by AWOL Reason: 1
Quote
a= 01
b= 11
c = (a/2 * b/2)*2 + (a%2 * b%2);


c = (0 * 1)* 2  + (1 * 1) = (0 * 2) + 1 = 1

Quote
So either robtillaart is wrong, or I am wrong.

Which also is a binary proposition.
I'll leave you to figure that one.

Quote
(1/2 * 3/2)*2 + (1%2 * 3%2) = 2.5

It's a two bit machine - difficult to represent fractions and two bits of significance in two bits.
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

robtillaart

#11
Jun 11, 2012, 07:16 pm Last Edit: Jun 11, 2012, 07:26 pm by robtillaart Reason: 1
Quote
Is a (01) and b (11) binary intergers, or decimal intergers?

The number a and b are meant as binary numbers. I should have written:

a= b01
b= b11
c = (a/2 * b/2)*2 + (a%2 * b%2);    // 8 operators

c = (0 * 1)* 2 + ( 1 * 1) = 0 + 1 = 1 == 01     ==>   c = b & a = 01 & 11 = 01

Quote
Also, % (modulo) is not regular math.

Since when? What is regular math according to you?

intermezzo regular math?
A multiplication is a repeated addition, and an addition is a repeated increment by 1.
so in the end everything is repeated an increment by 1 (that sounds like a turing machine!!)


% can be expressed as a subtraction, division and a multiply.  a % b = ( a - (a/b)*b)

a= b01
b= b11
c = (a/2 * b/2)*2 + (a- (a/2)*2)  * (b- (b/2)*2);   // 12 operators

Furthermore I assumed the integer division, which makes  1/2 =>  0

So yes, I was wrong taking not enough time to explain this properly ;)
(just like this post)

update
So if you want to rewrite bit operators to regular math you must first
1) isolate the individual digits
2) do the [AND-OR-XOR-NAND-....] operation
3) merge the outcomes

1 bit AND :  (a*b)
1 bit OR : (a+b - (a*b))
1 bit XOR:  (a+b - a*b *2)
1 bit NAND: 1-a*b
1 bit NOR: a*b - a - b
1 bit NXOR: 2*a*b -a - b

Formula's for ANDing 3 bits numbers (higher) is left as an exercise for the reader


Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

dkl65


What is regular math according to you?

Arithmetic that can be done with a standard calculator. Add, subtract, multiply, divide, square root are the only operations on a standard calculator. Powers are also accepted.
Visit http://www.glenof.webs.com/!

AWOL

Children are sometimes given dictionaries that miss out all the "rude" words.
Just because your calculator doesn't include all arithmetic operation doesn't mean modulo operations are not members of the set of arithmetic operations.
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

robtillaart

as shown above you only need  subtract add and multiply  for the bit operation

for the isolation of a single bits you need (multiple) division(s) and subtractions.

for the merge the + and * are used.

The isolation of bit n can be done by the formula :  a/ipow(2,n) - (a/ipow(2,n+1))*2    

ipow is an integer power (can by optimized by using consts 1,2,4,8,16, etc)

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Go Up