Division is computationally expensive (for example, in ARM chips add and subtract take 1 cycle. multiply takes 3 cycles. division takes 34). However, sometimes there are much faster ways to do things normally done with division. Let's take a look.
So, there are operations in computers called bitwise functions. They either apply logic gates to a number or reposition a number.
The ones in python are (I'll explain them in a minute)
a >> b which shifts a right by b amount
a << b which shifts a left by b amount
a & b which gives the logical AND of a and b (this is the one we'll actually use here though I briefly explain all but negation)
a | b which gives the logical OR of a and b
a ^ b which gives the logical XOR of a and b
~ a which gives the logical NOT of a
- a which gives the negative of a (negation is different than subtraction to a computer) I won't be explaining this concept here (maybe I'll go into 1's and 2's complements later).
Let's work with 6-bit binary numbers
Here's the numbers 0-15 and their 4-digit binary equivalents. The extra zeroes in the front are used to make the numbers the same amount of digits long.
00 0000
01 0001
02 0010
03 0011
04 0100
05 0101
06 0110
07 0111
08 1000
09 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
a = 13
that's 001101 in binary
b = 55
that's 110111
c = 3
that's 000011
a >> c shifts the bits in 'a' right 3 times since c = 3 (or does all three at the same time, but we'll do it step by step)
001101 # no shift
000110 # that's the first shift. 0's are added to the left and any 1's at the end are lost. 'a' is now 6 (which is 13/2 as remainders are dropped)
000011 # that's shift 2. 'a' is now 3 (which is 6/2)
000001 # that's shift 3, so 'a' is now equal 1 (which is 3/2)
a << (c -1) shifts the bits in 'a' to the left 2 times
001101
011010 #first shift. a = 26 (2 * 13)
110100 #second shift. a = 52 (26 * 13)
If I had shifted a third time, the one on the left would have been dropped because my number would be too big (called an overflow error)
logic gates take two inputs and give one output
AND (only outputs 1 when all inputs are 1's)
a b | output
0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1
OR (outputs 1 except when all inputs are 0's)
a b | output
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1
XOR (stands for exclusive OR. Only inputs with an odd number of 1's output a 1)
a b | output
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0
NOT (while most gates can take any amount of numbers, NOT only takes one argument)
a | output
1 | 0
0 | 1
Now let's do a & b (a AND b)
001101
110111 # find the bitwise AND. Each column is it's own miniature AND function.
000101 #only two columns were all 1's, so only those output a 1. (another way to do this is recognize that any column with a 0 outputs 0)
for a | b (a OR b)
001101
110111 # find the bitwise OR. Each column is it's own miniature OR function.
111111 # since every column had a 1, the answer was all 1's (the easy way here is that any column with a 1 outputs a 1)
for a ^ b (XOR, don't confuse with the power symbol in many languages and TI calculators)
001101
110111 # find the bitwise XOR. Each column is it's own miniature XOR function.
111010 #only columns with an odd number of 1's output 1
~a
001101
110010 # just make all 1's into 0's and all 0's into 1's
Try the AND, OR, and XOR for a,b, and c together yourself
001101
110111
000011
the answers are
AND 000001
OR 111111
XOR 111001
Now let's take a look at your loop. Notice that all the odd numbers end in a 1 and all even numbers end in 0.
Let's say that your user inputs a number (which the computer converts to binary). No matter how many bits are used, the last bit will be 1 if the number is odd. We need a way to find out if that last digit is odd or even. The answer is to AND it to 00000001 (or however many zeroes you need to be long enough, but the computer will add them as needed). Let's look at the numbers 44, 35, 52 and 23 when they're ANDed with 1.
101100 #44
000001 #now we AND
000000 #the even number outputs zero
100011 #35
000001 #now we AND
000001 #the odd number outputs one
110100 #52
000001 #now we AND
000000 #the even number outputs zero
010111 #23
000001 #now we AND
000001 #the odd number outputs one
Based on this, we can now say
Code:
x = int(input("start: ")) # don't forget to tell python to change the input from a string into an integer
y = int(input("end: "))
if 1 == (x & 1): # then the number is odd
while (x <= y): # if our initial value of x is bigger than y, then we will output nothing
print(x)
x = x + 2 # odd no. plus even no. equals another odd no.
else:
x = x + 1 # since x must be even, we add one to it to make it odd while staying within our parameters
while (x <= y):
print(x)
x = x + 2
Edited by hajile - 9/12/12 at 7:06pm
but I doubt he, as a beginner, is really asking for the information you are providing.
