Divide a Binary Number

WBahn

Joined Mar 31, 2012
29,976
Does your son know how to divide multi-digit decimal numbers by hand, such as

206901 / 873

The steps involved are identical to how you work with binary numbers (or any other number base). So if this isn't an issue, then the only issue is converting the decimal numbers to binary in the first place. There are a few ways to do it, but perhaps the easiest conceptually (though by far not the most efficient) is to just use the definition of a positional numbering system.

If your binary number is written as

x = hgfedcba

where each letter is either a 0 or a 1, then the "weight" of the 'a' bit is 2^0 = 1, the weight of the 'b' bit is 2^1 = 2, the weight of the 'c' bit is 2^2 = 4, and so on up through 'h' being 2^7 = 128.

This is the same as in decimal were the right-most digit has a weight of 10^0 = 1, the next digit 10^1 = 10, the next one 10^2 = 100, and so on.
 

ErnieM

Joined Apr 24, 2011
8,377
Most any windows PC should have a calculator program. If you hunt thru the menu you will find a scientific calculator, and that can be set to work in binary. You can even change modes to do a conversion, or enter 7 in decimal, change to binary and get 111.

The problem should be done on paper using old fahioned long division but this can help you check each step.
 

ian field

Joined Oct 27, 2012
6,536
Most any windows PC should have a calculator program. If you hunt thru the menu you will find a scientific calculator, and that can be set to work in binary. You can even change modes to do a conversion, or enter 7 in decimal, change to binary and get 111.

The problem should be done on paper using old fahioned long division but this can help you check each step.
Being a bit flash - I have a couple of calculators that work in various number bases.

They're at least 10 digit display, but you still cant do much in binary.
 

StacyB

Joined May 19, 2016
1
The first thing you need to do is convert the number to binary.

So 72 would be 1001000.

then to divided by 12 you would first divide the number by 4 and then by 3.

To divide by 4 you would shift the number 2 bits to the right. So 1001000 becomes 10010(18).

Then to divide by 3 you would divide by 2 and then subtract binary 3. Dividing by 2 again 10010 becomes 1001(9). Then subtracting 11(3) 1001 becomes 110 or 6.

To divide 100 by 5 you would divide by 4 by shifting the number 2 bits to the right and then subtract binary 5.

So dividing by 4 1100100(100) becomes 11001(25) and then subtracting 101(5) 11001 becomes 10100 or 20.
 

MrChips

Joined Oct 2, 2009
30,706
The first thing you need to do is convert the number to binary.

So 72 would be 1001000.

then to divided by 12 you would first divide the number by 4 and then by 3.

To divide by 4 you would shift the number 2 bits to the right. So 1001000 becomes 10010(18).

Then to divide by 3 you would divide by 2 and then subtract binary 3. Dividing by 2 again 10010 becomes 1001(9). Then subtracting 11(3) 1001 becomes 110 or 6.

To divide 100 by 5 you would divide by 4 by shifting the number 2 bits to the right and then subtract binary 5.

So dividing by 4 1100100(100) becomes 11001(25) and then subtracting 101(5) 11001 becomes 10100 or 20.
Totally wrong.

Who told you this? Or are you simply doing the shifts and correcting the result by subtracting what is left over?
Try your algorithm with different numbers and see if it still works.

BTW - Two months later, I think the OP is not coming back.
 

hp1729

Joined Nov 23, 2015
2,304
How can I Divide a Binary Number,
Exp: 72/12 & 100/5,
the Answers need to be in Binary...
Do the math in decimal then convert the answer ti binary,
Use a scientific calculator that does binary.

You do it the same way you do decimal. First convert the numbers to binary.
Then divide one number into the other just like you would if they were decimal.

Google "binary division".
 
Last edited:

jpanhalt

Joined Jan 18, 2008
11,087

ErnieM

Joined Apr 24, 2011
8,377
As long as this thread left the tracks long ago...

Once I had one rather short program to fit in a tiny micro controller with but one simple division to perform, something like a 16 bit number divided by an 8 bit, both unsigned. When using a C compiler I found that adding the one division made the program just large enough not to fit in my device. I had to use that device for many other reasons.

The work around was to do division by subtraction, literally count how many times I could subtract B from A and still get a positive result.

I had plenty of time to accomplish this task so a simple way worked out just fine.
 

joeyd999

Joined Jun 6, 2011
5,234
As long as this thread left the tracks long ago...

Once I had one rather short program to fit in a tiny micro controller with but one simple division to perform, something like a 16 bit number divided by an 8 bit, both unsigned. When using a C compiler I found that adding the one division made the program just large enough not to fit in my device. I had to use that device for many other reasons.

The work around was to do division by subtraction, literally count how many times I could subtract B from A and still get a positive result.

I had plenty of time to accomplish this task so a simple way worked out just fine.
Not that it matters wrt to this thread, but division doesn't take all that much code. Here's an old 48 bit/24 bit routine I have lying around. It's be smaller for 16/8.

Code:
;*************************************
;** DIV48x24 -- 48bit / 24 bit      **
;** OPER15:10 = PROD5:0 / OPER02:00 **
;*************************************

div48x24
	movlf	bitcnt,25		;set 24 bit division

clrquo	clrf	oper10
	clrf	oper11
	clrf	oper12
	clrf	oper13

	movfw	oper00			;make sure divisor is not zero (will hang)
	iorwf	oper01,w
	iorwf	oper02,w
	bz	normal			;do fake div without normalizing

	clrc
nordom	bbs	oper02,7,0,normal
	rlcf	oper00,f
	rlcf	oper01,f
	rlcf	oper02,f
	incf	bitcnt,f
	bra	nordom
	
normal	clrf	divhi

divlp	movfw	oper00
	subwf	prod3,w
	movwf	divtmp0

	movfw	oper01
	subwfb	prod4,w
	movwf	divtmp1
	
	movfw	oper02
	subwfb	prod5,w
	movwf	divtmp2
	
	clrw
	subwfb	divhi,w

	bm	divneg

	movwf	divhi
	movff	divtmp2,prod5
	movff	divtmp1,prod4
	movff	divtmp0,prod3

divneg	rlcf	oper10,f
	rlcf	oper11,f
	rlcf	oper12,f
	rlcf	oper13,f
	rlcf	oper14,f
	rlcf	oper15,f

	rlcf	prod0,f
	rlcf	prod1,f
	rlcf	prod2,f
	rlcf	prod3,f
	rlcf	prod4,f
	rlcf	prod5,f
	rlcf	divhi,f	

	djnz	bitcnt,divlp

	return
 

ErnieM

Joined Apr 24, 2011
8,377
Agreed. Somewhere I pasted a compiler output for some simple division routine that could have worked, but since I fairly work in assembler any more maintaining C code in a C project is far preferable to me, and whomever might have picked up that task now that I have left that company.
 

atferrari

Joined Jan 6, 2004
4,764
Are you asking about integer division, or do you need an expression for the remainder? Is this purely academic or do you need to write a program?

For "human" binary division, here is a worked example: http://www.exploringbinary.com/binary-division/

For programming, I was intrigued by this discussion of an algorithm for integer multiplication and division attributed Kenyans (and others): http://www.piclist.com/techref/method/math/muldiv.htm

Scan down to the section on novel methods.

John
Hola John

For the pleasure of it, I wrote the code to implement it with the 18F family. It worked at the first try.

Code:
Assembly   

;DIV 216U KENYAN.ASM


DIV_3216U_KEN               ;unsigned 32/16-bit values division (KENYAN)

;Agustin T. Ferrari Nicolay - Buenos Aires - April 2007

;Algorithm implemented:

;Given DIVIDEND and DIVISOR, initialize QUOTIENT =0 and INDEX_DSOR =0

;Duplicate DIVISOR repeatedly. Increase PNTR_DSOR every time DIVISOR is doubled

;Repeat doubling to get a DSOR equal to, or the closest below DIVIDEND.

;Substract the highest DSOR from DIVIDEND setting b0 of QUOTIENT.

;Shift QUOTIENT to left and decrement PNTR_DSOR.

;Succesively try to substract from the resulting remainder above, every DIVISOR

;value, down in the list.

;For every possible substraction, keep setting b0 of QUOTIENT and shifting it

;to left. If not possible, just shift QUOTIENT to the left.

;In any case, always decrement PNTR_DSOR.

;Once finished (PNTR_DSOR again =0), the remainder is the result of the last

;substraction. QUOTIENT in the corresponding register.


;To call the routine:
;dividend in DEND_3:0 (max val H'FFFE 0001' = H'FFFF' * H'FFFF' =4.294.836.225)
;divisor in DSOR_1:0 (max value H'FFFF' =65.535) - DSOR_3:2 used internally in
;the routine

;User to ensure being within range or if division by zero is attempted.

;The routine gives:
;Result of DEND_3:DEND_0 / DSOR_1:DSOR_0 => QUOT_H:QUOT_L.
;Remainder in DEND_3:0

    CLRF DSOR_3
    CLRF DSOR_2
    CLRF QUOT_H
    CLRF QUOT_L
    CLRF PNTR_DSOR

DIV_3216U_KEN_INC_DSOR_LOOP
    BCF STATUS,C            ;ensure b0 of DSOR_0 is clear after the shifting
    RLCF DSOR_0,F           ;DSOR =DSOR*2
    RLCF DSOR_1,F
    RLCF DSOR_2,F
    RLCF DSOR_3,F
   
    INCF PNTR_DSOR,F

    MOVF DSOR_3,W
    SUBWF DEND_3,W
    BNZ CHKIF_DSOR3_GT_DEND3
   
    MOVF DSOR_2,W
    SUBWF DEND_2,W
    BNZ CHKIF_DSOR2_GT_DEND2
   
    MOVF DSOR_1,W
    SUBWF DEND_1,W
    BNZ CHKIF_DSOR1_GT_DEND1
   
    MOVF DSOR_0,W
    SUBWF DEND_0,W
    BC DIV_3216U_KEN_INC_DSOR_LOOP
   
DIV_3216U_KEN_SUBST_DSOR_LOOP
    TSTFSZ PNTR_DSOR
    BRA DIV_3216U_KEN_DECR_PNTR
    RETURN

DIV_3216U_KEN_DECR_PNTR
    DECF PNTR_DSOR          ;we look down in the list of double DSOR values
   
    BCF STATUS,C            ;ensure b0 of QUOT_L is clear after shifting
    RLCF QUOT_L,F           ;shift QUOT to the left to have it ready
    RLCF QUOT_H,F           ;for next substraction

    BCF STATUS,C            ;ensure b7 of DSOR_3 is clear after shifting
    RRCF DSOR_3,F           ;shift DSOR
    RRCF DSOR_2,F           ;to the right
    RRCF DSOR_1,F           ;to get
    RRCF DSOR_0,F           ;DSOR =DSOR/2

    MOVF DSOR_3,W
    SUBWF DEND_3,W
    BNZ CHKIF_DSOR3_LT_DEND3
   
    MOVF DSOR_2,W
    SUBWF DEND_2,W
    BNZ CHKIF_DSOR2_LT_DEND2
   
    MOVF DSOR_1,W
    SUBWF DEND_1,W
    BNZ CHKIF_DSOR3_LT_DEND3
   
    MOVF DSOR_0,W
    SUBWF DEND_0,W
    BNC DIV_3216U_KEN_SUBST_DSOR_LOOP

DIV_3216U_KEN_SUBST_DSOR    ;substract DSOR_3:0 from DEND_3:0
    MOVF DSOR_0,W           ;LSB, borrow
    SUBWF DEND_0,F          ;is NOT used

    MOVF DSOR_1,W           ;borrow
    SUBWFB DEND_1,F         ;IS used

    MOVF DSOR_2,W           ;borrow
    SUBWFB DEND_2,F         ;IS used

    MOVF DSOR_3,W           ;borrow
    SUBWFB DEND_3,F         ;IS used

    BSF QUOT_L,0            ;flag "a valid substraction from dividend occurred"
    BRA DIV_3216U_KEN_SUBST_DSOR_LOOP

CHKIF_DSOR3_GT_DEND3
    BNC DIV_3216U_KEN_SUBST_DSOR_LOOP
    BRA DIV_3216U_KEN_INC_DSOR_LOOP

CHKIF_DSOR2_GT_DEND2
    BNC DIV_3216U_KEN_SUBST_DSOR_LOOP
    BRA DIV_3216U_KEN_INC_DSOR_LOOP

CHKIF_DSOR1_GT_DEND1
    BNC DIV_3216U_KEN_SUBST_DSOR_LOOP
    BRA DIV_3216U_KEN_INC_DSOR_LOOP

CHKIF_DSOR3_LT_DEND3
    BC DIV_3216U_KEN_SUBST_DSOR
    BRA DIV_3216U_KEN_SUBST_DSOR_LOOP

CHKIF_DSOR2_LT_DEND2
    BC DIV_3216U_KEN_SUBST_DSOR
    BRA DIV_3216U_KEN_SUBST_DSOR_LOOP

CHKIF_DSOR1_LT_DEND1
    BC DIV_3216U_KEN_SUBST_DSOR
    BRA DIV_3216U_KEN_SUBST_DSOR_LOOP
 
Top