forked from 7harshit20/dsa
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bit_manipulation.cpp
129 lines (121 loc) · 2.29 KB
/
bit_manipulation.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <math.h>
using namespace std;
int getbit(int n, int pos) {
return (n & (1 << pos)) == 0 ? 0 : 1;
}
int setbit(int n, int pos)
{
return (n | (1 << pos));
}
int clearbit(int n, int pos)
{
// return (n & ~(1<<pos));
return ~(~n | (1 << pos));
}
int updatebit(int n, int pos, int value)
{
return clearbit(n, pos) | value << pos;
}
bool ispowerof2(int n)
{
// int i=0;
// while(getbit(n,i)==0)i++;
// return n==(1<<i);
return n && !(n & (n - 1));
}
int totalone(int n)
{
int num=0;
while(n)
{
n=(n & n - 1);
num++;
}
return num;
}
void subsets(int n, char arr[])
{
for(int i=0; i < pow(2, n); i++)
{
for(int j=n - 1; j >= 0; j--)
{
if(getbit(i, j))
cout << arr[n - 1 - j];
}
cout << endl;
}
}
int unique(int arr[], int n)
{
int xorsum=0;
for(int i=0; i < n; i++)
{
xorsum=xorsum ^ arr[i];
}
return xorsum;
}
void twounique(int arr[], int n)
{
int xorsum=0;
for(int i=0; i < n; i++)
{
xorsum^=arr[i];
}
int i=0;
while(xorsum & (1 << i) == 0)
i++;
int fn=0;
for(int i=0; i < n; i++)
{
if(arr[i] & (1 << i))
{
fn^=arr[i];
}
}
cout << fn << endl;
// int sn=0;
// for(int i=0;i<n;i++){
// if(arr[i]==fn)continue;
// sn^=arr[i];
// }
cout << (fn ^ xorsum) << endl;
}
int uniquefromthree(int arr[], int n)
{
int digits[32]={ 0 };
for(int i=0; i < 32; i++)
{
for(int j=0; j < n; j++)
{
if(getbit(arr[j], i))
{
digits[i]++;
}
}
digits[i]=digits[i] % 3;
}
int num=0;
for(int i=0; i < 32; i++)
{
num+=(pow(2, i) * digits[i]);
}
return num;
}
int main()
{
// cout<<(1<<3)<<endl;;
// cout<<getbit(11,2)<<endl;
cout << setbit(4, 0) << endl;
// cout<<clearbit(5,2)<<endl;
// cout<<updatebit(5,1,1)<<endl;
// cout<<ispowerof2(0);
// cout<<totalone(7);
// char arr[]= {'a','b','c','d','e'};
// subsets(5,arr);
// int arr[]={55,3,55,3,55,3,1,1,99,1};
// cout<<unique(arr,11);
// twounique(arr,8);
// cout<<uniquefromthree(arr,10);
return 0;
}