In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, division by
two or halving has also been called mediation or dimidiation. The treatment of this as a different operation from multiplication and division by other numbers goes back to the ancient Egyptians, whose
multiplication algorithm used division by two as one of its fundamental steps.
Some mathematicians as late as the sixteenth century continued to view halving as a separate operation, and it often continues to be treated separately in modern
computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...
.
[.]
Performing this operation is simple in
decimal arithmetic
The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
, in the
binary numeral system
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" ( zero) and "1" (one).
The base-2 numeral system is a positional notati ...
used in computer programming, and in other even-numbered
bases.
Binary
In binary arithmetic, division by two can be performed by a
bit shift operation that shifts the number one place to the right.
This is a form of
strength reduction optimization. For example, 1101001 in binary (the decimal number 105), shifted one place to the right, is 110100 (the decimal number 52): the lowest order bit, a 1, is removed. Similarly, division by any
power of two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent.
In a context where only integers are considered, is restricted to non-negat ...
2
''k'' may be performed by right-shifting ''k'' positions. Because bit shifts are often much faster operations than division, replacing a division by a shift in this way can be a helpful step in
program optimization
In computer science, program optimization, code optimization, or software optimization, is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources. In general, a computer program may be o ...
.
However, for the sake of
software portability
A computer program is said to be portable if there is very low effort required to make it run on different platforms. The pre-requirement for portability is the generalized abstraction between the application logic and system interfaces. When ...
and readability, it is often best to write programs using the division operation and trust in the
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...
to perform this replacement. An example from
Common Lisp
Common Lisp (CL) is a dialect of the Lisp programming language, published in ANSI standard document ''ANSI INCITS 226-1994 (S20018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived fr ...
:
(setq number #b1101001) ; #b1101001 — 105
(ash number -1) ; #b0110100 — 105 >> 1 ⇒ 52
(ash number -4) ; #b0000110 — 105 >> 4 ≡ 105 / 2⁴ ⇒ 6
The above statements, however, are not always true when dealing with dividing
signed binary numbers. Shifting right by 1 bit will divide by two, always rounding down. However, in some languages, division of signed binary numbers round towards 0 (which, if the result is negative, means it rounds up). For example,
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mo ...
is one such language: in Java,
-3 / 2
evaluates to
-1
, whereas
-3 >> 1
evaluates to
-2
. So in this case, the compiler ''cannot'' optimize division by two by replacing it by a bit shift, when the dividend could possibly be negative.
Binary floating point
In binary
floating-point arithmetic
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
, division by two can be performed by decreasing the exponent by one (as long as the result is not a
subnormal number). Many programming languages provide functions that can be used to divide a floating point number by a power of two. For example, the
Java programming language
Java is a high-level, class-based, object-oriented programming language that is designed to have as few implementation dependencies as possible. It is a general-purpose programming language intended to let programmers ''write once, run anywh ...
provides the method
java.lang.Math.scalb
for scaling by a power of two, and the
C programming language
''The C Programming Language'' (sometimes termed ''K&R'', after its authors' initials) is a computer programming book written by Brian Kernighan and Dennis Ritchie, the latter of whom originally designed and implemented the language, as well a ...
provides the function
ldexp
for the same purpose.
[, Section 7.12.6.6.]
Decimal
The following
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
is for decimal. However, it can be used as a model to construct an algorithm for taking half of any number ''N'' in any
even
Even may refer to:
General
* Even (given name), a Norwegian male personal name
* Even (surname)
* Even (people), an ethnic group from Siberia and Russian Far East
**Even language, a language spoken by the Evens
* Odd and Even, a solitaire game wh ...
base.
*Write out ''N'', putting a zero to its left.
*Go through the digits of ''N'' in overlapping pairs, writing down digits of the result from the following table.
Example: 1738/2=?
Write 01738. We will now work on finding the result.
* 01: even digit followed by 1, write 0.
* 17: odd digit followed by 7, write 8.
* 73: odd digit followed by 3, write 6.
* 38: odd digit followed by 8, write 9.
Result: 0869.
From the example one can see that
0 is even.
If the last digit of ''N'' is
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
digit one should add 0.5 to the result.
See also
*
One half
One half ( : halves) is the irreducible fraction resulting from dividing one by two or the fraction resulting from dividing any number by its double. Multiplication by one half is equivalent to division by two, or "halving"; conversely ...
*
Median
In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic f ...
, a value that splits a set of data values into two equal subsets
*
Bisection
In geometry, bisection is the division of something into two equal or congruent parts, usually by a line, which is then called a ''bisector''. The most often considered types of bisectors are the ''segment bisector'' (a line that passes throug ...
, the partition of a geometric object into two equal halves
*
Dimidiation, a heraldic method of joining two coats of arms by splitting their designs into halves
References
{{reflist
Division (mathematics)
Elementary arithmetic
Binary arithmetic
Parity (mathematics)
2 (number)