Yesterday I read a very interesting article “China is escalating its punishment diplomacy” by Jamil Anderlini in the Financial Times. If you did not get a chance to read it, please do so. You will be surprised how open China is manipulating politicians all over the world.
Another article of interest might be “China sharply expands mass labor program in Tibet” by Cate Cadell in Reuters. The Chinese communist government is picking up people in Tibet, teaching and deploying them to work in groups all over China. The article seems to validate the idea that the cost of manufacturing in China is going up and in order to continue to attract companies to manufacture in China, they need cheap labor. China uses a 72-hour work week which is getting expensive, and in order to continue to be the single provider of globalization, they need to get cheap labor.
In a nutshell, before you vote on the next presidential elections, you need to
make sure you have the facts and elect the proper candidate. America and in general the free world depends on it.
Enough said, let’s take a look at the main subject of this post.
I looked for a problem in LeetCode and problem 29 Divide Two Integers look like a winner. In reality is more of a random selection.
Let’s take a look at the requirements.
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2. Notes: Both dividend and divisor will be 32-bit signed integers. The divisor will never be 0. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.
We need to implement integer division without using multiplication, division or the modulus operation. The result should truncate towards zero. Make sure you take note on how overflow is indicated in the returned value. The values should fit in a 32-bit integer. That indicates that we might not need to use long variables.
public int divide(int dividend, int divisor) {
}
With the requirements in mind, we see that the function we need to implement requires two operands. One will be the dividend and the other the divisor. The function should return the integer result of the operation.
10,3 main <<< dividend: 10 divisor: 3 main <<< divide: 3 7,-3 main <<< dividend: 7 divisor: -3 main <<< divide: -2 2,2 main <<< dividend: 2 divisor: 2 main <<< divide: 1 43,-8 main <<< dividend: 43 divisor: -8 main <<< divide: -5 2147483647,2147483647 main <<< dividend: 2147483647 divisor: 2147483647 main <<< divide: 1 -2147483648,-2147483648 main <<< dividend: -2147483648 divisor: -2147483648 main <<< divide: 1 -2147483648,-1 main <<< dividend: -2147483648 divisor: -1 main <<< divide: 2147483647 2147483647,-2147483648 main <<< dividend: 2147483647 divisor: -2147483648 main <<< divide: 0 -2147483648,2147483647 main <<< dividend: -2147483648 divisor: 2147483647 main <<< divide: -1 1,-1 main <<< dividend: 1 divisor: -1 main <<< divide: -1 -1,1 main <<< dividend: -1 divisor: 1 main <<< divide: -1 1,1 main <<< dividend: 1 divisor: 1 main <<< divide: 1 -1,-1 main <<< dividend: -1 divisor: -1 main <<< divide: 1 -2147483648,2 main <<< dividend: -2147483648 divisor: 2 main <<< divide: -1073741824 1,3 main <<< dividend: 1 divisor: 3 main <<< divide: 0 10,3 main <<< dividend: 10 divisor: 3 main <<< divide: 3 4,10 main <<< dividend: 4 divisor: 10 main <<< divide: 0 1234,5678 main <<< dividend: 1234 divisor: 5678 main <<< divide: 0
I have a few examples. Some were provided by LeetCode the others by me. Note that we are provided the dividend and the divisor. We just need to return the result.
As usual I will implement my own test scaffolding. I like to work on my machine with the tools I use for work. In my case I will use the Java programming language, the VSCode IDE and will develop and test the code on a Windows 10 computer.
Make sure you try different examples to check that your code makes sense and will be accepted. I tried a single approach with two variants. I then started on a different approach. After a while I decided to punt. Found some information about bit operations and did some experimenting. Also found a mechanism to extract the binary of an integer that did not work as expected. I left an on-line comment.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** display max and min integer values ****
// System.out.println("main <<< MAX_VALUE: " + Integer.MAX_VALUE);
// System.out.println("main <<< MIN_VALUE: " + Integer.MIN_VALUE);
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read dividend & divisor ****
String[] dd = sc.nextLine().split(",");
// **** close scanner ****
sc.close();
// **** convert to integer ****
int dividend = Integer.parseInt(dd[0]);
int divisor = Integer.parseInt(dd[1]);
// ????? ????
System.out.println("main <<< dividend: " + dividend + " divisor: " + divisor);
// **** generate and display result ****
System.out.println("main <<< divide: " + divide(dividend, divisor));
}
We start by displaying the max and min values for integers. They were used to generate some test cases. The two lines have been commented out.
We read a string and split it. The first value represents the dividend and the second the divisor. We display the values to make sure all is well and call the divide() function. We print the returned value.
/**
* Given two integers dividend and divisor,
* divide two integers without using multiplication,
* division and mod operator.
*/
static int divide(int dividend, int divisor) {
// **** check for overflow ****
if ((dividend == Integer.MIN_VALUE) && (divisor == -1))
return Integer.MAX_VALUE;
// **** check if dividing by 1 ****
if (divisor == 1)
return dividend;
// **** check if dividend equals divisor ****
if (dividend == divisor)
return 1;
// **** keep track of sign for the quotient ****
int sign = 1;
// **** check sign on dividend ****
if (dividend < 0)
sign *= -1;
// **** check sign on divisor ****
if (divisor < 0)
sign *= -1;
// **** make both values positive ****
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
// **** initialize the quotient ****
int quotient = 0;
// **** loop subtracting divisor from dividend ****
while (dividend - divisor >= 0) {
// **** update quotient ****
quotient++;
// **** update dividend ****
dividend -= divisor;
}
// **** loop subtracting divisor from dividend ****
// while (dividend - divisor >= 0) {
// // **** exponent ****
// int x = 0;
// // **** how many times we can subtract (divisor ^ 2) ****
// while (dividend - (divisor << 1 << x) >= 0) {
// x++;
// }
// // **** update quotient (2 ^ x) ****
// quotient += (1 << x);
// // **** update dividend (divisor ^ x) ****
// dividend -= (divisor << x);
// }
// **** return quotient with proper sign ****
return sign * quotient;
}
We start by performing a set of checks.
We then set the variable sign to generate the sign for the returned value.
It is simpler to make the arguments positive. We set the quotient to zero (0) and are ready to enter a loop.
The approach we are taking is to subtract the divisor from the dividend until 
we can no longer do so. Each time we need to increase the quotient. This is the way division works. Please take a few moments to make sure you understand the logic of the process.
As usual, there are possible optimizations. The commented code is one of them; or is not? The idea in the commented out loop is to reduce the number of times we loop in the outer loop. We do so by multiplying the divisor by a power of two. The idea is that we could skip testing intermediate values.
As soon as we get a negative value, we drop out of the small loop and adjust the value we delete from the divisor.
The outer loop continues as long as the difference between the dividend and the divisor is >= 0.
I submitted both approaches to LeetCode. The simpler and more elegant (uncommented) loop performed better.
I kept on searching and reading about division. Found an on-line book “Hacker’s Delight Second Edition” by Henry S. Warren, Jr. that has a lot of information about dealing with bits on a computer. I took the time to order a copy from Amazon. The book will be arriving this coming Saturday. I will start reading the book Sunday. Will let you know my thoughts in a future post.
/**
* Given two integers dividend and divisor,
* divide two integers without using multiplication,
* division and mod operator.
*
* !!!! WORK IN PROGRESS - RUN OUT OF TIME !!!!
*/
static int divide1(int dividend, int divisor) {
// **** ****
BigInteger a = new BigInteger(Integer.toString(dividend), 10);
BigInteger b = new BigInteger(Integer.toString(divisor), 10);
// ???? ????
System.out.println("divide1 <<< a: 0x" + a.toString(2));
System.out.println("divide1 <<< b: 0x" + b.toString(2));
// **** c = a / b ****
BigInteger c = a.divide(b);
// ???? ????
System.out.println("divide1 <<< c: 0x" + c.toString(2));
// **** divide the numbers ****
double d = (double)dividend / (double)divisor;
// ???? ????
System.out.println("divide1 <<< d: " + d);
// **** get integral part of double ****
int integral = (int)d;
// ???? ????
System.out.println("divide1 <<< integral: " + integral);
// **** get fractional part of double ****
double fractional = d - integral;
// ???? ????
System.out.println("divide1 <<< fractional: " + fractional);
// **** convert and display fractional to binary (seems to have an issue) ****
System.out.println("divide1 <<< fractional: " + Long.toBinaryString(Double.doubleToRawLongBits(fractional)));
// **** convert and display fractional to binary ****
String lStr = "";
double f = fractional;
System.out.print("divide1 <<< f: ");
for (int i = 0; i < 54; i++) {
f *= 2;
System.out.print((int)f);
lStr += "" + (int)f;
f -= (int)f;
}
System.out.println();
// ???? ????
System.out.println("divide1 <<< lStr: " + lStr);
// **** ****
return 0;
}
This function is not used in the solution. This represents a second approach at solving the problem. It was taking too long and had to get back to work so I left it for a future post. Will first read more about techniques in the book I ordered and then will give it a shot.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 2631 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa