Saturday, June 25, 2011

implement Bit operation for setting & re-setting the bit in range & at ith position

Operations are
Set(i) sets the ith bit O(1)
Unset(j) unsets the jth bit Set(i,j) O(1)
sets the bits b/w i and j Unset(i,j) o(logn)..??
unsets the bits b/w i and j O(logn) ???
Design a data structure for this problem with minimum time and space complexity.

#include
int set(int N,int i){
N = N | (1<=j;k--){
N = set(N,k);
}
return N;
}

int main(){

int N=7;
int i=3,j=2;
N=set(N,i);
printf("%d\n",N);

N=unset(N,j);
printf("%d\n",N);
N=set_range(0,3,1);
printf("%d\n",N);
/*unset(N,i,j);*/
return 0;
}

Time Complexity O(n)
Space Complexity O(1)

Optmization O(logn)
Yes we can use RMQ mechenism to do this , Segment Tree is Awesome Option to set upper bound for set(i,j,) & unset(i,j) will be O(logn)

No comments :