Negation
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/***************************************************************************
 * Author: Isai Damier
 * Title: Negation
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a set of bits, x, find its negation.
 *
 * Sample Input:  0101100
 * Sample Output: 1010011
 *
 * Technical Details:
 *   The negation of a set x is the set comprising all the elements in the
 *   universe that are not in x. For example if the context is all the
 *   ciphers in the decimal system and s1 = [0,2,5,8] then the negation of
 *   s1 is [1,3,4,6,7,9]. For a set of bits the negation is simply the
 *   bitwise NOT of the set. For example if x = 0110101 then the
 *   negation of x is 1001010.
 *
 * Alternate Algorithm:
 *   The negation of a set of bits x may also be calculated as ALL_BITS ^ x,
 *   where ^ is the bitwise XOR operator. For example, if x = 0110101 then
 *   perforce ALL_BITS = 1111111. Hence, negative x = 1111111^0110101=1001010
 *
 * JAVA Note:
 *   Java does not support unsigned numbers. Therefore, there are times when
 *   ~x must be replaced with ALL_BITS^x in order to work properly. The
 *   programmer must define ALL_BITS. If x is an integer, for example, then
 *   ALL_BITS is a string of sixteen ones.
 **************************************************************************/
 public int negation(int x) {
  int u = Integer.parseInt(""1111111111111111"", 2);
  return u^x;// or return ~x
}