// Power Set
import Foundation

infix operator >>>> : BitwiseShiftPrecedence

extension Int {

    var binaryString: String {
        return convertToBinaryString(size: Int.bitWidth)
    }

    func convertToBinaryString(size: Int) -> String {
        let mask = 0b1 << (size - 1)
        let signBit = ( mask & self ) != 0 ? "1" : "0"
        let number = ~mask & self
        let binaryForm = String(number, radix: 2)
        return signBit + String(repeatElement("0", count: size - binaryForm.count - 1)) + binaryForm
    }

    static func >>>> (lhs: Int, rhs: Int) -> Int {
        let mask = ~( ~0 << (Int.bitWidth - rhs))
        return ( lhs >> rhs ) & mask
    }
}

func calculate(mask: Int, start: Int, end: Int) {

    for i in start..<end {
        let val = 1 << i
        let result = (val | mask)
        let newStart = start - 1
        if newStart >= 0 {
            let newMask = result & ~(1 << newStart)
            calculate(mask: newMask, start: newStart, end: i)
        } else {
            print(result.binaryString)
        }
    }
}

func calculate(n: Int, size: Int) {
    if size > Int.bitWidth {
        return
    }
    if n == 0 {
        print(0.binaryString)
        return
    }
    let start = n - 1
    let mask = (1 << start) - 1
    let end = size
    calculate(mask: mask, start: start, end: end)

}

calculate(n: 2, size: 3)