bit manipulation
1.find decimal to binary without using any data structure.
import java.io.*;
import java.util.*;
class GFG
{
static String fun(int a)
{
if(a==0)
{
return "0";
}
String st="";
while(a>0)
{
String temp= (a & 1)==1 ? "1": "0";
st=temp + st;
a=a>>1;
}
return st;
}
//Integer.toBinaryString(23);
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int p=sc.nextInt();
String s=fun(p);
System.out.println(s);
}
}
2.find binary to decimal without using Math.pow().
import java.io.*;
import java.util.*;
class gfg
{
static int fun(String s1)
{
int a=0;
int base=1;
for(int i=0;i<s1.length();i++)
{
//a=a+(Character.getNumericValue(s1.charAt(s1.length()-i-1)))*(int)Math.pow(2,i);
a=a+Character.getNumericValue(s1.charAt(s1.length()-i-1))*base;
base=base*2;
}
return a;
}
//int foo = Integer.parseInt("1001", 2);
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
int a=fun(s);
System.out.print(a);
}
}
3.Check k th bit is set or not in a binary number
static int fun(int s1,int k)
{
s1= s1 & (1<<(k-1));
return s1; //it will be true if bit will be set
}
4.set k th bit of a binary number
static int fun(int s1,int k)
{
s1= s1 | (1<<(k-1)); //it will set k th bit .
return s1;
}
5.Reset k th bit of a binary number
static int fun(int s1,int k)
{
s1= s1 & ~(1<<(k-1));
return s1;
}
6.Toggle the kth bit
static int fun(int s1,int k)
{
s1= s1 ^ (1<<(k-1));
return s1;
}
7. Toggle rightmost 1 to 0
static int fun(int s1)
{
s1= s1 & (s1 -1);
return s1;
}
8.Separate the rightmost 1 to lsd or Isolate rightmost 1 bit
static int fun(int s1)
{
s1= s1 & (-s1 );
return s1;
}
9.check number is power of two or not
static int fun(int s1,int k)
{
s1= s1 & s1-1;
return s1; //if it will zero than power of 2
}
NOTE
//To count no of 1 IN A INTEGER=> int count = count + table[n & 0xF]
1.check number is power of four or not.
class Solution
{
public boolean isPowerOfFour(int num)
{
if(num==1)
{
return true;
}
else if(num>3 && Integer.bitCount(num)==1)
{
int temp=(int)(Math.log(num)/Math.log(2));
if(temp%2==0)
{
return true;
}
else
{
return false;
}
}
return false;
}
}
// return (num>0) && (num & (num-1))==0 && (715827882 & num)==0;
715827882=1010101010
2.Number of 1 Bits
public class Solution {
public int hammingWeight(int n)
{
int count=0;
while(n!=0)
{
count++;
n=n&(n-1);
}
return count;
}
}
3 sum of two number without using +,- operator.
class Solution
{
public int getSum(int a, int b)
{
while(b!=0)
{
int c=a & b;
a=a ^ b;
b=c<<1;
}
return a;
}
}
3 reverse bit
Input: 43261596
Output: 964176192
Explanation: 43261596 represented in binary as 00000010100101000001111010011100,
return 964176192 represented in binary as 00111001011110000010100101000000.
Output: 964176192
Explanation: 43261596 represented in binary as 00000010100101000001111010011100,
return 964176192 represented in binary as 00111001011110000010100101000000.
public int reverseBits(int n)
{
/* StringBuffer s1=new StringBuffer(Integer.toBinaryString(n));
while(s1.length()<32)
{
s1.insert(0,0);
}
s1.reverse();
return Integer.parseUnsignedInt(s1.toString(),2);
*/
int result=0;
for(int i=0;i<32;i++)
{
int d=n & 1;
result=result<<1;
result=result | d;
n=n>>1;
}
return result;
}
4.find the difference
s = "abcd"
t = "abcde"
Output:
e
t = "abcde"
Output:
e
public char findTheDifference(String s, String t)
{
//return (char)(t.chars().sum() -s.chars().sum());
int sum=0;
for(int i=0;i<s.length();i++)
{
sum=sum+ s.charAt(i);
}
for(int i=0;i<t.length();i++)
{
sum-=t.charAt(i);
}
return (char)Math.abs(sum);
}
Swap all odd and even bits
public static void swap_even_and_odd_bit(int n)
{
int n1=0xAAAAAAAA & n <<1;
int n2=0x55555555 & n >>1;
int k=n1 | n2;
System.out.println(k);
}
Convert to Roman No
void convertToRoman(int n)
{
String[] m={"","M","MM","MMM"};
String[] c{"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
String[] t={"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
String[] i={"","I","II","III","IV","V","VI","VII","VIII","IX"};
String thousand=String.valueOf(m[(n/1000)]);
String hundred=String.valueOf(c[(n%1000)/100]);
String ones=String.valueOf(i[n%10]);
String ten=String.valueOf(t[n%100/10]);
String s1=thousand + hundred + ten +ones;
System.out.println(s1);
}
Graph: Bfs
import java.io.*;
import java.util.*;
class GFG
{
LinkedList<Integer> adj[];
int V;
GFG(int v)
{
V=v;
adj=new LinkedList[v];
for(int i=0;i<v;i++)
{
adj[i]=new LinkedList<Integer>();
}
}
public void addEdge(int v,int w)
{
adj[v].add(w);
}
public void DFSUtil(boolean[] visited,int j)
{
visited[j]=true;
//System.out.println(j+" ");
//remove comment line for dfs
LinkedList<Integer> queue=new LinkedList<Integer>();
queue.add(j);
while(queue.size()!=0)
{
int n=queue.poll();
System.out.print(n+" ");
Iterator<Integer> it=adj[n].listIterator();
while(it.hasNext())
{
int p=it.next();
if(!visited[p])
{
visited[p]=true;
queue.add(p);
}
}
}
/* dfs
Iterator<Integer> it=adj[j].listIterator();
while(it.hasNext())
{
int n=it.next();
if(!visited[n])
{
DFSUtil(visited,n);
}
}
*/
}
public void DFS(int j)
{
boolean[] visited=new boolean[V];
DFSUtil(visited,j);
}
public static void main(String[] args)
{
GFG g=new GFG(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.DFS(2);
}
}
Comments
Post a Comment