Member Avatar for Alex Edwards

How in the hell do you divide by 7 using nothing but--

~, ^, >>, <<, &, |

-- In a set algorithm. I'm stumped.

I've tried mapping out different numbers dividing by each other... it didn't work.

I would map out a number subtracting from the other to see if there is some kind of pattern. I thought there was, but I think it varies based on whether the number is odd or not.

It's also hard to be accurate if the divisor being a prime number, odd number or even number matters.


This isn't required for anything. I just want to know how to think in the right direction to approach this.

If needed I'll write out what I've tried.

Edit: Might as well do it--

First: Thought that every number has a set pattern for division so I tried several tests.

15 / 3 = 5


   1111 = 15
/  0011 = 3
----------
   0101 = 5


Pattern(theory, from the left) -> bitAnd, bitXor || bitIor, bitXor, bitAnd || bitIor

Still too many unknowns and possibilities with the potential "others" so I tried again with smaller numbers

8/2 = 4


  1000 = 8
/ 0010 = 2
------------
  0100 = 4

Pattern(theory, from the left) -> bitAnd, ???? || ~result, bitAnd, bitANY

Fairly inconsistent.


From there I was just about to stop, but I realized that it may be possible that numbers used for division that are the result of n continuous binary digits can be resolved to a pattern--

SUM (n-> a real number): 2^n
[1, 3, 7, 15, 31, 63, 127, 255, ...]

63 / 7 = 9

  111111 = 63
/ 000111 = 7
------------
  001001 = 9

Pattern(theory, from the left) -> bitAnd, bitAnd, bitXor || bitIor, bitXor, bitXor, bitAnd || bitIor

These results are fairly good, but semi-consistent with the first result.

Then again there probably couldn't be a set result since numbers will vary in length.


I believe that--

*There must be some "knock-off" determinant. Basically the length (or value) of the resultant number must be some binary function of the initial number and the divisor.

*That there most likely is a pattern but I'm just not seeing it. It could be some kind of circular-pattern dealing with the bit operations (for all real values).


This is just a hunch without any thorough research. I think I'll try continuously subtracting numbers to see if there is some kind of pattern.
  • 4 Contributors
  • 8 Replies
  • 171 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by invisal
Member Avatar for Alex Edwards

And if possible, please don't remove this! I will try to code it in C++ >_>

Member Avatar for vijayan121 
#include <iostream>
#include <limits>

// addition can be done using bitwise xor
// with adjustments for carry bits
unsigned int plus( unsigned int first, unsigned int second )
{
  unsigned int carry = first & second ; // the carry bits
  unsigned int result = first ^ second ; // the result bits

  while( carry ) // loop over the carry bits
  {
    carry <<= 1U ; // shift carry to next bit
    unsigned int temp = result ^ carry ;
    carry &= result ;
    result = temp ;
  }

  return result;
}

// to subtract, add the two's complement
unsigned int minus( unsigned int first, unsigned int second )
{
  unsigned int carry = ~second & 1U ;
  unsigned int twos_complement = ~second ^ 1U ;

  while( carry )
  {
    carry <<= 1U ;
    unsigned int temp = twos_complement ^ carry ;
    carry &= twos_complement ;
    twos_complement = temp;
  }

  return plus( first, twos_complement ) ;
}

int main()
{
  enum { RADIX = std::numeric_limits<unsigned int>::radix } ;
  struct check_it { char static_assert[ RADIX == 2 ? 1 : -1 ] ; } ;

  for( int i=0 ; i<10 ; ++i )
  {
    unsigned int a = std::rand()%1000 ;
    // a*7 === ( a*8 - a ) === ( a*4 + a*2 + a )
    std::cout << a << " * 7  = " << minus( a<<3U, a ) << " ("
       << plus( a<<2U, plus( a<<1U, a ) ) << ") (" << a*7 << ")\n" ;
  }
}
commented: You've got quite a head on your shoulders =P +1
Member Avatar for Alex Edwards 
#include <iostream>
#include <limits>

// addition can be done using bitwise xor
// with adjustments for carry bits
unsigned int plus( unsigned int first, unsigned int second )
{
  unsigned int carry = first & second ; // the carry bits
  unsigned int result = first ^ second ; // the result bits

  while( carry ) // loop over the carry bits
  {
    carry <<= 1U ; // shift carry to next bit
    unsigned int temp = result ^ carry ;
    carry &= result ;
    result = temp ;
  }

  return result;
}

// to subtract, add the two's complement
unsigned int minus( unsigned int first, unsigned int second )
{
  unsigned int carry = ~second & 1U ;
  unsigned int twos_complement = ~second ^ 1U ;

  while( carry )
  {
    carry <<= 1U ;
    unsigned int temp = twos_complement ^ carry ;
    carry &= twos_complement ;
    twos_complement = temp;
  }

  return plus( first, twos_complement ) ;
}

int main()
{
  enum { RADIX = std::numeric_limits<unsigned int>::radix } ;
  struct check_it { char static_assert[ RADIX == 2 ? 1 : -1 ] ; } ;

  for( int i=0 ; i<10 ; ++i )
  {
    unsigned int a = std::rand()%1000 ;
    // a*7 === ( a*8 - a ) === ( a*4 + a*2 + a )
    std::cout << a << " * 7  = " << minus( a<<3U, a ) << " ("
       << plus( a<<2U, plus( a<<1U, a ) ) << ") (" << a*7 << ")\n" ;
  }
}

I ran the program and see that it works!

Now let's see...

For a number a, there is an N such that--

(using 7 as an example divisor)

a / 7 = N

( a / 7 ) - N = 0;

( a / 7 ) - N + 1 = 1; // not expecting to divide by zero

a - (7*N) + 7 = 7; // if( N != 0)

a - (7*N) = 0; // if( N != 0)

So to divide by a number, you need to know how many times the number occurs, which can be done by constant subtraction and monitoring how many passes it takes to reach zero when subtracting.

I'm pretty sure this is doable with your above method, however I'd have to find out how to capture the remainder amount somehow...

It's also reasonable to say that this is impossible for N = 0, but then again this was stated before I believe.

Member Avatar for invisal

Mathematically, you can just constantly substract the dividend with divisor and count it until the dividend become smaller than the divisor. If dividend become 0 after it's been constantly substracted, it means that the dividend is divisible to divisor. If dividend is bigger than 0, then it is a remainder.

For example:

  • 23 / 7 = ???
  • 23 - 7 = 16 (1 time)
  • 16 - 7 = 09 (2 time)
  • 09 - 7 = 02 (3 time, stop substracting because 2 is smaller than 7)
  • So 23 / 7 = 3 with remainder 2
Member Avatar for ctrl-alt-del

Mathematically, you can just constantly substract the dividend with divisor and count it until the dividend become smaller than the divisor. If dividend become 0 after it's been constantly substracted, it means that the dividend is divisible to divisor. If dividend is bigger than 0, then it is a remainder.

For example:

  • 23 / 7 = ???
  • 23 - 7 = 16 (1 time)
  • 16 - 7 = 09 (2 time)
  • 09 - 7 = 02 (3 time, stop substracting because 2 is smaller than 7)
  • So 23 / 7 = 3 with remainder 2

modulus would apply to this right? (the "%")

Member Avatar for invisal

modulus would apply to this right? (the "%")

int a = 46, b = 3, c;
for (c = 0; a >= b; c++)
   a -= b;
// in the end, a will be remainder, c will be the result of the division.
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.