비트 조작
일일 학습
오늘은 비트 조작에서 몇 가지 트릭을 배웠고 같은 것을 공유하고 싶습니다.
중요한 공식
x<<y x>>y 비트 조작은 이를 사용하여 공간 복잡성을 줄일 수 있기 때문에 공간 제약이 있을 때 매우 유용합니다.
-------------------------------------------------- ----------
회문인 문자열의 하위 시퀀스를 생성하려면
첫 번째 작업은 하위 시퀀스를 생성하는 것입니다(일부 문자를 제거한 후 문자열의 일부입니다). 다음은 회문인지 여부를 확인하는 것입니다.
Generate palindromic Subsequences from a given string
질문에 대한 코드
#include<bits/stdc++.h>
using namespace std;
bool ispalindrome(string s)
{
int i=0;
int j=s.length()-1;
while(i<j)
{
if(s[i]==s[j])
{
i++;
j--;
}
else
return false;
}
return true;
}
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int count=0;
int n=s.length();
for(int i=0;i< (1<<n);i++) //it will generate pow(2,n) subsequences
{
string temp="";
for(int j=0;j<n;j++)
{
int x=(1<<j);
if((x&i)!=0)
{
// cout<<s[j];
temp+=s[j];
}
}
//cout<<endl;
if(temp!="")
{
//cout<<temp<<endl;
if(ispalindrome(temp))
count++;
}
}
cout<<(count+1)<<endl;
}
}
Hackerearth Link
Another application of Bit Manipulation is when you are given few numbers and you need to check sum of the difference in bits between any two numbers.
For Example: 3 2 4 011 010 100 answer is 12질문에 대한 코드
#include <iostream>
#include <vector>
# include <cstring>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
for(int k=1;k<=t;k++)
{
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++)
cin>>arr[i];
int bitset[32];
memset(bitset,0,sizeof(bitset));
for(int i=0;i<32;i++)
{
for(int j=0;j<n;j++)
{
int x=(1<<i);
if(arr[j]&x)
bitset[i]++;
}
}
long long int res=0;
for(int i=0;i<32;i++)
{
res+=bitset[i]*(n-bitset[i]);
if(res>10000007)
res=res%10000007;
}
res=2*res;
if(res>10000007)
res=res%10000007;
cout<<"Case "<<k<<": ";
cout<<res<<endl;
}
return 0;
}
질문 출처:SPOJ
link
원천 :
Reference
이 문제에 관하여(비트 조작), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/powercoder/bit-manipulation-5b11텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
