Bitwise math

[bigbass]

Hello guys

We have a few examples of bitwise math "being used "
for encoding and decoding but not stand alone code
focusing on each part such as ADD ,SUBTRACT, MULTIPLY ,DIVIDE
in just bitwise code that will compile in bacon
and could be used as a stand alone function


later I will use some built in bacon commands ROR(), ROL() to multiply and divide only by 2
this is the same as shift left or right << >> in c

ADD

'---using only bitwise logic to add two numbers

'==============================================
FUNCTION ADD(int x, int y)
'==============================================
LOCAL c TYPE int
 WHILE x != 0
 
carry = y & x
y = y ^ x
x = carry << 1            
 WEND


RETURN y
ENDFUNCTION

PRINT ADD(2, 13)





SUBTRACT

'---using only bitwise logic to subtract two numbers
'==============================================
FUNCTION SUBTRACT(int y, int x)
'==============================================

LOCAL carry TYPE int
 WHILE x != 0
 
carry = ~y & x
y = y ^ x
x = carry << 1              
 WEND


RETURN y
ENDFUNCTION

PRINT SUBTRACT(8, 13)




MULTIPLY

'---using bitwise logic to multiply two numbers

'==============================================
FUNCTION MULTIPLY(int x, int y)
'==============================================
LOCAL carry TYPE int
LOCAL result TYPE int
 '--- While second number doesn't become 1  
 WHILE y > 0
'---If second number becomes odd, add the first number to result
IF (y & 1) THEN
result = result + x
 
ENDIF


'--- Double the first number and halve the second number
x = x << 1
y = y >> 1  

 WEND


RETURN result
ENDFUNCTION

PRINT MULTIPLY(3, 4)








I want to do an easier division example
rosettacode.org/wiki/Egyptian_division#

[vovchik]

Dear Joe,

Thanks for those examples. I have attached some bitwise functions I did some time ago. They might just be useful for your collection.

With kind regards,
vovchik

Attachments:

bit_funcs.bac_20180824.tar.gz (1.92 KB)

[bigbass]

Hello vovchik

Thanks!

I saw the date and wondered
how I forgot about those or
I just missed them somehow
but its good having a collection of
small functions that take care of
these low level bits

there are many c code examples of
encoders and the fastest always use
bitwise math with some type of masking
and it would be nice to recognize
what is going on at the bit level


the multiply is a shorted way of doing the math
I want to do a short divided by also
maybe on the weekend have a lot to do today

Joe

[bigbass]

I dont think we can make a shorter or faster rot13
that isnt the focus here the focus is using some built in c functions
we can baconize easily and explain some bitwise math
and it will be easy to reuse code for other ascii filtering




' example using built in isalpha() from c  
' we can baconize this easily... hint
' https://www.tutorialspoint.com/c_standard_library/ctype_h.htm

' and uses a bitwise OR to check the ascii range

' ------------------
FUNCTION ROT13$(char* s)
' ------------------
LOCAL o$ TYPE STRING
LOCAL a, i TYPE int
FOR i = 0 TO LEN(s) -1
   
   a = s[i]
   

   IF (isalpha(a) == 0) THEN
       '--- is not a letter of the alphabet
       o$ = o$ & CHR$(a)
   ELSE
       '--- is an alphabet letter
       '--- OR with 32 to force uppercase to lowercase then add 13
   IF ((a  | 32 ) + 13) > 122 THEN
       o$ = o$ & CHR$(a - 13)
   ELSE  
       o$ = o$ & CHR$(a  + 13)
   END IF
END IF

NEXT i
RETURN o$
END FUNCTION


PRINT ROT13$("Gur dhvpx oebja sbk whzcf bire 13 ynml qbtf !@#$%^&*()_+-")



[bigbass]

well just cant get enough of this decoding stuff
this time even shorter with ctypes.h bacon has this header already included
but it's pure c


' example using built in isalpha() from c  
' we can baconize this easily... hint
' https://www.tutorialspoint.com/c_standard_library/ctype_h.htm

' ------------------
FUNCTION ROT13$(char* s)
' ------------------
LOCAL o$ TYPE STRING
LOCAL a, i TYPE int
FOR i = 0 TO LEN(s) -1
   
           a = s[i]
   o$ = o$ & CHR$(isalpha(a)?tolower(a)<'n'?a+13:a-13:a)
   
NEXT
RETURN o$
END FUNCTION

PRINT ROT13$("Gur dhvpx oebja sbk whzcf bire 13 ynml qbtf" )



[bigbass]

just to have uppercase basic looking syntax without a lot of
converting header code doing all the renaming and macros

we reuse already working c functions
the problem with ascii is you have to work out all the ranges again
and it wont be easily readable when you finish

just a simple alias will do fine here

ALIAS isalnum  TO ISALNUM
ALIAS tolower  TO TOLOWER



then just to test it with the post above


ALIAS isalnum  TO ISALNUM
ALIAS isalpha  TO ISALPHA
ALIAS iscntrl  TO ISCNTRL
ALIAS isdigit  TO ISDIGIT
ALIAS isgraph  TO ISGRAPH
ALIAS islower  TO ISLOWER
ALIAS isprint  TO ISPRINT
ALIAS ispunct  TO ISPUNCT
ALIAS isspace  TO ISSPACE
ALIAS isupper  TO ISUPPER
ALIAS isxdigit TO ISXDIGIT
ALIAS tolower  TO TOLOWER
ALIAS toupper  TO TOUPPER

'isalnum Tests whether a character is alphanumeric or not
'isalpha Tests whether a character is aplhabetic or not
'iscntrl Tests whether a character is control or not
'isdigit Tests whether a character is digit or not
'isgraph Tests whether a character is graphic or not
'islower Tests whether a character is lowercase or not
'isprint Tests whether a character is printable or not
'ispunct Tests whether a character is punctuation or not
'isspace Tests whether a character is white space or not
'isupper Tests whether a character is uppercase or not
'isxdigit Tests whether a character is hexadecimal or not
'tolower Converts to lowercase if the character is in uppercase
'toupper Converts to uppercase if the character is in lowercase


' example using built in isalpha() from c  
' we can baconize this easily... hint
' https://www.tutorialspoint.com/c_standard_library/ctype_h.htm

' ------------------
FUNCTION ROT13$(char* s)
' ------------------
LOCAL o$ TYPE STRING
LOCAL a, i TYPE int
FOR i = 0 TO LEN(s) -1
   
        a = s[i]
   o$ = o$ & CHR$(ISALPHA(a)? TOLOWER(a) < 'n' ? a + 13 :a - 13 :a)
         
NEXT
RETURN o$
END FUNCTION

PRINT ROT13$("Gur dhvpx oebja sbk whzcf bire 13 ynml qbtf" )








[vovchik]

Dear Joe,

Thanks. Those are all useful functions and the ALIASes make them look native. I have been a silent lately since I am trying to fix some hardware problems...I hope it all is working soon.

With kind regards,
vovchik

[bigbass]

Hello vovchik

hope you get the hardware problem sorted quickly
also look for capacitors that the top is bubbled up and not flat
they can go bad on older boards at least they are easy to replace if that's the problem

here is a fun way to look at bitwise division from another point of view
rosettacode.org/wiki/Egyptian_division


I shortened the code to one function and used 3 arguments
and removed the pointer for the remainder
now it will print a remainder or not depending on the third argument


EGYPTIAN_DIVISION(580,34,1)





'---Ported from rosetta code egytian division c code example to BaCon by bigbass
'---http://rosettacode.org/wiki/Egyptian_division

'==================================================================================
FUNCTION EGYPTIAN_DIVISION(long dividend, long divisor, long remainder) TYPE long
'==================================================================================
'--- remainder is the third  parameter, pass 0 if you do not need the remainder

DECLARE powers[64] TYPE long
DECLARE doublings[64] TYPE long

LOCAL i TYPE long

FOR i = 0 TO  63 STEP 1  
powers[i] = 1 << i
doublings[i] = divisor << i
IF (doublings[i] > dividend) THEN
BREAK
ENDIF
NEXT

LOCAL answer TYPE long
LOCAL accumulator TYPE long
answer = 0
accumulator = 0

WHILE i >= 0
'--- If the current value of the accumulator added to the
'--- doublings cell would be less than or equal to the
'--- dividend then add it to the accumulator
IF (accumulator + doublings[i] <= dividend) THEN
accumulator = accumulator + doublings[i]
answer = answer + powers[i]
ENDIF
DECR i
WEND

IF remainder THEN
remainder = dividend - accumulator
PRINT dividend ," / ", divisor , " = " , answer ," remainder " , remainder
ELSE
PRINT dividend ," / ", divisor , " = " , answer
ENDIF

RETURN answer

ENDFUNCTION


'--- the large number divided by the smaller number
'--- the third argument is 1 if you want to have a remainder
'--- and 0 if you dont want to have a remainder

EGYPTIAN_DIVISION(580,34,1)
EGYPTIAN_DIVISION(580,34,0)
 


 


[vovchik]

Dear Joe,

Thanks. I knew nothing about the Egyptian method. is it normal for it to be off with the remainder?

EGYPTIAN_DIVISION(580,34,1)
PRINT "NORMAL 580 / 34 = ", 580/34
PRINT "NORMAL 580.0 / 34.0 = ", 580.0/34.0
EGYPTIAN_DIVISION(580,34,0)

With kind regards,
vovchik

[bigbass]

Hello vovchik


An excellent question how to interpret the remainder to mean something
really I had no clue so had to play with the numbers to see a pattern



Do I get extra credit to solve a 4000 year old mystery ?
I played with a fraction table until I saw some part of a pattern
happening
then I saw that I needed to add back the remainder and bingo !

It makes sense now how to read it
added it to the BaCon rosetta page


100 / 95 = 1 remainder 5
PRINT "NORMAL 100.0 / 95.0 = ", 100.0/95.0
PRINT "remainder / divisor + answer ", 5.0/95.0 +1

run the code it will generate all the answers

Joe

'---Ported from rosetta code egytian division c code example to BaCon by bigbass
'---http://rosettacode.org/wiki/Egyptian_division

'==================================================================================
FUNCTION EGYPTIAN_DIVISION(long dividend, long divisor, long remainder) TYPE long
'==================================================================================
'--- remainder is the third  parameter, pass 0 if you do not need the remainder

DECLARE powers[64] TYPE long
DECLARE doublings[64] TYPE long

LOCAL i TYPE long

FOR i = 0 TO  63 STEP 1  
powers[i] = 1 << i
doublings[i] = divisor << i
IF (doublings[i] > dividend) THEN
BREAK
ENDIF
NEXT

LOCAL answer TYPE long
LOCAL accumulator TYPE long
answer = 0
accumulator = 0

WHILE i >= 0
'--- If the current value of the accumulator added to the
'--- doublings cell would be less than or equal to the
'--- dividend then add it to the accumulator
IF (accumulator + doublings[i] <= dividend) THEN
accumulator = accumulator + doublings[i]
answer = answer + powers[i]
ENDIF
DECR i
WEND

IF remainder THEN
remainder = dividend - accumulator
PRINT dividend ," / ", divisor, " = " , answer ," remainder " , remainder

       PRINT "Decoded the answer to a standard fraction"
       PRINT  (remainder + 0.0 )/ (divisor + 0.0) + answer
       PRINT

ELSE
PRINT dividend ," / ", divisor , " = " , answer
ENDIF

RETURN answer

ENDFUNCTION


'--- the large number divided by the smaller number
'--- the third argument is 1 if you want to have a remainder
'--- and 0 if you dont want to have a remainder

'EGYPTIAN_DIVISION(580,34,1)
'EGYPTIAN_DIVISION(580,34,0)

'EGYPTIAN_DIVISION(580,34,1)
PRINT
PRINT
EGYPTIAN_DIVISION(100,95,1)
PRINT
EGYPTIAN_DIVISION(100,85,1)
PRINT
EGYPTIAN_DIVISION(100,75,1)
PRINT
EGYPTIAN_DIVISION(100,65,1)
PRINT
EGYPTIAN_DIVISION(100,55,1)
PRINT
EGYPTIAN_DIVISION(100,45,1)
PRINT
EGYPTIAN_DIVISION(100,35,1)
PRINT
EGYPTIAN_DIVISION(100,25,1)
PRINT
EGYPTIAN_DIVISION(100,15,1)
PRINT
EGYPTIAN_DIVISION(100,10,1)
PRINT
EGYPTIAN_DIVISION(100,5,1)
PRINT




 

100 / 95 = 1 remainder 5
Decoded the answer to a standard fraction
1.05263


100 / 85 = 1 remainder 15
Decoded the answer to a standard fraction
1.17647


100 / 75 = 1 remainder 25
Decoded the answer to a standard fraction
1.33333


100 / 65 = 1 remainder 35
Decoded the answer to a standard fraction
1.53846


100 / 55 = 1 remainder 45
Decoded the answer to a standard fraction
1.81818


100 / 45 = 2 remainder 10
Decoded the answer to a standard fraction
2.22222


100 / 35 = 2 remainder 30
Decoded the answer to a standard fraction
2.85714


100 / 25 = 4 remainder 0
Decoded the answer to a standard fraction
4


100 / 15 = 6 remainder 10
Decoded the answer to a standard fraction
6.66667


100 / 10 = 10 remainder 0
Decoded the answer to a standard fraction
10


100 / 5 = 20 remainder 0
Decoded the answer to a standard fraction
20