CareerCup

#include<stdio.h>
2
3 void two_1s_no_generator(unsigned int num)
4
5 {
6 int count=0,bol_val;
7
8 int i,j;
9
10 unsigned int mask;
11
12 for(j=1;j<=num;j++)
13
14 {
15 mask=1<<31;
16 count=0;
17
18 for(i=1;i<=32;i++)
19
20 {
21 bol_val= j&mask?1:0;
22
23 if(bol_val==1)
24 count++;
25
26 mask=mask>>1;
27
28
29 }
30
31 if(count == 2)
32 {
33 printf("%d ",j);
34
35 }
36 }
37 printf("\n\n");
38 }
39 int main()
40
41 {
42 unsigned int num;
43
44 printf("Enter the Range :");
45
46 scanf("%d",&num);
47
48 two_1s_no_generator(num);
49
50 }

You know, there is C(n, 2) such n-bit integers, so with N ~ 10^14 output value can be order of 2^(10^7), so problem is not just about "bit manipulation".

Solution: lets look at numbers MSB. There is exactly k numbers in this sequence with MSB at position k (1 for MSB = 2^1 (3), 2 for MSB = 2^2 (5,6) and so on). Inside of this blocks of increasingly larger sizes, LSB goes from 0 to k-1.
So, formal solution is following:
- define k = min x : x*(x+1)/2 >= N
- define p = k*(k+1)/2 - N
Answer is 2^k + 2^(k - p - 1).

#include<stdio.h>
  2 
  3 int print_two_ones_no(int x)
  4 
  5 {
  6     
  7     int count=0;
  8     
  9     int num = x;
 10     
 11     while(x)
 12     
 13     {
 14         x = x&(x-1);
 15 
 16             count++;
 17     
 18     }
 19     
 20     if(count == 2)
 21 
 22         printf("%d ",num);
 23 
 24 }
 25 
 26 int main()
 27 
 28 {
 29 
 30     int num,i;
 31 
 32     printf("Enter the Range :");
 33 
 34     scanf("%d",&num);
 35 
 36     for(i=1;i<=num;i++)
 37 
           {
 39 
 40     print_two_ones_no(i);
 41 
 42     }
 43 
 44 }
                                                                                 17,0-1        Top

// NOT FOR Competitive stuff - it is meaningless for practical purposes.
// but cool...
/* 
Given S is then sorted sequence of numbers such that 
Binary representation contains only 2 bits set to 1.
Find S(n). 
We solve it by creating an iterator.
*/
s = seq( 3 ) -> {
  bs = str($.p[-1],2)
  li = rindex(bs.value, _'1' )
  if ( li == 1 ){
     r = 2 ** #|bs| + 1 
  } else {
     bs.value[li] = _'0'
     bs.value[li-1] = _'1'
     r = int(bs,2,0)
  }
  r 
}
fold ( [1:9] ) -> { println( s.next ) }

#Consider the following sequence: 3, 5, 6, 9, 10, 12, 17, 18, 20....
#Write a function that takes n in range(1, 10**14) and returns the 
#nth term of the sequence

import math

def a(n):
    a = .5; b = .5; c = -n
    #use the quadratic formula to find the first i s.t. n <= i*(i+1)/2
    i = int(math.ceil( ( -b - math.pow( (b**2 - 4*a*c), .5 ) )/(2*a) ))
    if not (0 < i and i < n):
        i = int(math.ceil( ( -b + math.pow( (b**2 - 4*a*c), .5 ) )/(2*a) ) )
    #sum of first i numbers
    s = (i*(i+1)/2)
    offset = i - (s - n) - 1
    return (1 << i) + (1 << offset)
    
def b(n):
    s = 0; i = 0
    #use a loop to find the first i s.t. n <= i*(i+1)/2
    #the time to find such an i will grow according like O(sqrt(n))
    while True:
        if s >= n:
            break
        else:
            i += 1
            s += i
    offset = i - (s - n) - 1
    return (1 << i) + (1 << offset)

import math

def how_many_bits(x):
  count = 0
  while x:
    x = x & (x - 1)
    count += 1
  return count

def how_many_bit(x):
  return 1 + int(math.log(x,2))

def foo(x):
  top_bit = x&-x
  higher_bit_set = top_bit + x
  mask = higher_bit_set ^ x
  mask = mask>>how_many_bit(top_bit)
  mask = mask >> 1
  return mask + higher_bit_set

x = 3
for i in range(20):
  y = foo(x)
  print(y)
  if how_many_bits(y) != 2:
    print("something wrong", y, how_many_bits(y), bin(y))
  x = y

Boils down to solving arithmetic series and bit manipulation... but tricky

//C#
public static int GetTwoBitSequenceValue(int sequenceNumber)
{
    int bit2Position = (int) Math.Round(Math.Sqrt(sequenceNumber * 2), 0) - 1;
    int bit1Position = sequenceNumber - ((int)((bit2Position * (bit2Position + 1)) / 2) + 1);

    return (2 << bit2Position) | (1 << bit1Position); 
}

public static void Test()
{
    for (int i = 1; i < 20; i++)
    {
        int y = GetTwoBitSequenceValue(i);
        Console.WriteLine("x {0} => y {1}",i, y);
    }
}

Quite easy, solution in java in O(1) time working for any input

public static BigInteger getNthNumber(long n){
        int a = (int)Math.floor((1 + Math.sqrt(1 + 8 * n - 8)) / 2);
        int b = n - a * (a - 1) / 2 - 1;
        return BigInteger.ZERO.setBit(a).add(BigInteger.ZERO.setBit(b));
    }

public class BitWise {
public static void main(String...strings) {
int k = 2;
int currNo = 1, extra = 1, pow =1, base = (int) Math.pow(2, pow);
int seriesNo = base + extra;

while(true) {
System.out.println(seriesNo);
if(currNo == k)
break;

extra = extra << 1;
if(base == extra) {
pow++;
extra = 1;
base = (int) Math.pow(2, pow);
}
seriesNo = base + extra;
currNo++;
}
}
}

#include <stdio.h>

int main()
{
    int i,j,n,k;
    int imask=0;
    int jmask=0;
    //n bits number 
    n=8;
    //kth number
    k=6;
    int count=0;
    i=1;
    int allones=~0;
    
    while(i<n)
    {
        for(j=0;j<i;j++)
        {
            count++;
                //this is the number. i.e. i+1 are total number of bits with ith bit as 1 and jth bit as 1.
                imask=1<<i;
                jmask=1<<j;
                allones=allones & imask;
                allones=allones & jmask;
                printf("count %d - %d\n",count,imask | jmask);
            
        }
        i++;
    }
        
    
    

    return 0;
}

1 #include<stdio.h>
2
3 int print_two_ones_no(int x)
4
5 {
6
7 int count=0;
8
9 int num = x;
10
11 while(x)
12
13 {
14 x = x&(x-1);
15
16 count++;
17
18 }
19
20 if(count == 2)
21
22 printf("%d ",num);
23
24 }
25
26 int main()
27
28 {
29
30 int num,i;
31
32 printf("Enter the Range :");
33
34 scanf("%d",&num);
35
36 for(i=1;i<=num;i++)
37
38 {
39
40 print_two_ones_no(i);
41
42 }
43
44 }

1 #include<stdio.h>
  2 
  3 int print_two_ones_no(int x)
  4 
  5 {
  6 
  7     int count=0;
  8 
  9     int num = x;
 10 
 11     while(x)
 12 
 13     {
 14         x = x&(x-1);
 15 
 16             count++;
 17 
 18     }
 19 
 20     if(count == 2)
 21 
 22         printf("%d ",num);
 23 
 24 }
 25 
 26 int main()
 27 
 28 {
 29 
 30     int num,i;
 31 
 32     printf("Enter the Range :");
 33 
 34     scanf("%d",&num);
 35 
 36     for(i=1;i<=num;i++)
 37 
 38     {
 39 
 40     print_two_ones_no(i);
 41 
 42     }
 43 
 44 }

O(n) solution.

int Next2BitsNum(int n)
{
    int bit0 = 0;
    int bit1 = 1;
    int i;
    for (i = 0; i < n; i++)
    {
        bit0++;
        if (bit0 == bit1)
        {
            bit0 = 0;
            bit1++;
        }
    }

    return (1 << bit0) | (1 << bit1);
}

Some modification required???????

#include<stdio.h>
int main()
{
int N;
scanf("%d",&N);
int b,c,i;
int a[N];
a[0]=3;
int j=0;
for(i=1;i<N;i=i+2)
{
a[i]=(2*a[j])-1;
a[i+1]=2*(a[j]);
j=j+1;
}
printf("%d",a[N-1]);

}

Can you please comment the Question Link