ENCDEC03 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Shekhar Srivastava
Testers: Akash Kumar Bhagat, Sunita Sen

DIFFICULTY:

EASY

PREREQUISITES:

Bitwise operators, the binary number system

PROBLEM:

You will be given a number x and you have to perform four different operations on x.

  1. check i^{th} bit, if it is 1 print “ON” else print “OFF”.
  2. turn on the i^{th} bit.
  3. turn off the i^{th} bit.
  4. swap the p^{th} and the q^{th} bits.

for queries 1,2 and 3 you will be given the integer i, and for query 4 you will be given two integers p and q.

given 1 \leq i,p,q \leq 30 and 1 \leq x \leq 10^9

EXPLANATION:

We can use 32bit binary representation of x to solve this problem.

  1. Checking the i^{th} bit:
i. Right shift x (i-1)times and perform bitwise and with 1, the result is the i th bit.
         bit_at_i = (x>>(i-1))&1
ii. The number 2^(i-1) has only i th bit set, so if the result of bitwise and of 2^(i-1) and x is not zero or equal to 2^(i-1), then we can say that ith bit is 1.
          bit_at_i is on if ((1<<(i-1))&x)==(1<<(i-1))
  1. Turning on the i^{th} bit:
i. result of bitwise OR of x with 2^(i-1) will be x with ith bit 1 (as 2^(i-1) has only ith bit  set) .
         x |= (1<<(i-1))
  1. Turning off the i^{th} bit:
i. we perform bitwise and of x with a number with all bits set except the ith bit, that is the inverse of 2^(i-1).
         x = x&(~(1<<(i-1)))
ii. if we know that ith bit is 1, then bitwise XOR of x with 2^(i-1) will also result in x with ith bit 0.
          if(ith bit is 1) ->  x = x XOR (1<<(i-1))
  1. To swap the bit at p and q we can check their current status, if they are not the same then we can use operations 2 and 3 to change them.

If we use bitwise operations, each operation is a constant time operation.

Since we do not really need the decimal representation of x, we can also store its binary representation in an array and then perform the queries. This will require O(log x) preprocessing time and extra space.

SOLUTIONS:

Python
def operation(t):
    global a,x
    n=len(a)
    if t<4:
        y=n-int(input())
        if t==1:
            ans='ON' if a[y]=='1' else 'OFF'
            print(ans)
        if t==2:
            a[y]='1'
        if t==3:
            a[y]='0'
    else:
        p,q=map(int,input().split())
        a[n-p],a[n-q]=a[n-q],a[n-p]
     
 
for _ in range(int(input())):
    x,q=map(int,input().split())
    a=['0']*50+list(bin(x)[2:])
    for i in range(q):
        t=int(input())
        operation(t)
Python
# USING BITWISE OPERATIONS
def sf():
        def fo(x,y,z):
            b1 = (x>>(y-1))&1
            b2 = (x>>(z-1))&1 
            x = query[2 if b1 else 3](x, z)
            x = query[2 if b2 else 3](x, y)
            return x
        query = {
            1: lambda x,y : "ON" if ((x>>(y-1))&1)==1 else "OFF",       
            2: lambda x,y : x|(1<<(y-1)), #on
            3: lambda x,y : x&(~(1<<(y-1))), #off
            4: fo,
        }
  
        for _ in range(int(input())):
            x,q = map(int, input().split())
            for _ in range(q):
                qtype = int(input())
                args = [x] + list(map(int, input().split()))
                qq = query[qtype](*args)
                if qtype==1:print(qq)
                else: x=qq 
sf()