#======================================================================
# 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
#
#======================================================================
def negation( x ):
u = int( "1111111111111111", 2 )
return u ^ x # or return ~x
import unittest
from algorithms import bitwise as bits
class Test( unittest.TestCase ):
def testNegation( self ):
x = int( "1111111111111010", 2 )
r = int( "0000000000000101", 2 )
u = int( "1111111111111111", 2 )
self.assertEquals( r, bits.negation( x ) )
self.assertEquals( x, bits.negation( r ) )
self.assertEquals( u ^ x, r )
