Skip to content

Instantly share code, notes, and snippets.

@rogeliorv
Last active November 24, 2022 03:16
Show Gist options
  • Save rogeliorv/0a4b8e39d25a8d4707169fb81111ff8b to your computer and use it in GitHub Desktop.
Save rogeliorv/0a4b8e39d25a8d4707169fb81111ff8b to your computer and use it in GitHub Desktop.
Codility challenge get a base -2 number with the least significative bit at the left.
# Codility challenge for base -2 with the least significative bit at the left.
#
# In base -2 integers are represented by sequences of bits in the following way.
# Bits are ordered from the least to the most significant. Sequence B of N bits
# represents the number: sum(B[i] * (-2)^i for i = 0..N-1). The empty sequence represents 0.
# Note that such representation is suitable for both positive and negative numbers.
# NOTE: Remember negative division returns the floor. http://python-history.blogspot.mx/2010/08/why-pythons-integer-division-floors.html
# In regular english:
# You are given a binary number in the form of an array in base -2
# Base -2 works in the following way:
# Given an array A = [1,1,0,1,1]
# The number is: 1 + (-2) + 0 + (-8) + 16 = 7. The numbers come from the following operations.
# A[0] * -2 ^ 0 = 1 * 1 = 1
# A[1] * -2 ^ 1 = 1 *-2 = -2
# A[2] * -2 ^ 2 = 0
# A[3] * -2 ^ 3 = 1 *-8 = -8
# A[4] * -2 ^ 4 = 1 *16 = 16
# Given A = [1,1,0,1,1] = 7 (Decimal)
# We have to express now -7 in base -2
# Which would be [1, 0, 0, 1]
# A[0] * -2 ^ 0 = 1 * 1 = 1
# A[1] * -2 ^ 1 = 0
# A[2] * -2 ^ 2 = 0
# A[3] * -2 ^ 3 = 1 *-8 = -8
import math
def solution(bits):
decimal = getDecimalFromBits(bits)
bits = getBitsFromDecimal(-decimal)
return bits
def getBitsFromDecimal(number):
number = -number
result = []
while number != 0:
result.append(number % 2)
number /= -2
return result
def getDecimalFromBits(bits):
result = 0;
for index, bit in enumerate(bits):
# You can either use math.pow or ** the exponentiation operator
# Be careful to cover odd indices when using ** operator
result += bit * int(math.pow(-2, index))
return result
def test():
for number in range(0, 20):
bits = getBitsFromDecimal(number)
neg = getBitsFromDecimal(-number)
print "Number: %s -> Bits %s -%s bits: %s" % (number, bits, number, neg)
@rangathedon
Copy link

Hi, I was trying to solve this problem and came across your solution and looks like getBitsFromDecimal does not return a correct value; you can verify it by passing its result to getDecimalFromBits and it fails to give you back the same number!

@Ramadanko
Copy link

Hi,

May i have clarification please.
Decimal 7 should be
[0,1,1,1]
from right to left
why it is [1,1,0,1,1]
this is important please
would you mind having a call on skype, zoom or even phone ?

@rogeliorv
Copy link
Author

@rangathedon

Hi, I was trying to solve this problem and came across your solution and looks like getBitsFromDecimal does not return a correct value; you can verify it by passing its result to getDecimalFromBits and it fails to give you back the same number!

Tried range of data from -1000000 to 100000 and didnt find any differences. Can you provide such data ?

@rogeliorv
Copy link
Author

@Ramadanko

Hi,

May i have clarification please.
Decimal 7 should be
[0,1,1,1]
from right to left
why it is [1,1,0,1,1]
this is important please
would you mind having a call on skype, zoom or even phone ?

Hey! Remember this is base -2 (minus 2) not base 2 (plus 2)

7 in base 2 is 0111
7 in base -2 is 11011

You can follow a similar approach by changing the "-2" in the solution to your needs :)

@Ramadanko
Copy link

Yes. base -2 👍 sorry man and thanks

@shalahuddinn
Copy link

@rogeliorv hey man, what is the intuition behind this? number = -number why we do that?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment