Category Archives: Algorithm

分布式一致性算法02：Multi-Paxos

Posted on by — No Comments ↓

分布式一致性算法02 Multi-Paxos算法

一、基本概念
Multi-Paxos算法，在Paxos的基础上，通过引入领导者（Leader）的概念，大幅提升了效率。

二、Multi-Paxos算法通常涉及三种角色：
Leader（领导者）/Proposer（提议者） ：在Multi-Paxos中，通常会选举出一个Leader作为Proposer，负责提出提议，并尝试让多数接受者接受该提议。
Acceptor（接受者） ：负责接受或拒绝提议者的提议。每个节点都可以是Acceptor，负责记录和确认提议。
Learner（学习者） ：负责学习最终达成一致的提议。

三、Multi-Paxos算法的基本过程
1、初始化阶段
首先，通过Paxos算法，选择一个领导者（Leader），它负责发起全部提议。

2、准备阶段（Prepare Phase）
领导者向集群中的其他节点发送Prepare消息，这些消息包含当前的最大提议编号。
Acceptor（接受者）接收到Prepare消息后，会返回一个响应，表明它们是否已经接收到更高编号的提议。
如果领导者接收到大多数节点的响应，表示它们没有更高的提议，则可以继续下一步。

3、接受阶段（Accept Phase）
领导者根据收到的Prepare响应选择一个提议编号，并向集群中的其他节点发送Accept消息。这些消息包含提议编号和提议值。
节点接收到Accept消息后，如果该提议编号高于它们当前已接受的提议，则会接受该提议并返回确认消息。如果大多数节点确认接受该提议，则该提议被接受。

4、提交阶段（Commit Phase）
一旦提议被大多数节点接受，领导者将该提议标记为已提交，并通知集群中的其他节点。
节点接收到提交通知后，将执行该提议，并更新其状态。

5、应用阶段（Apply Phase）
最后，领导者将已提交的提议应用到状态机中，并通知集群中的其他节点。
节点接收到应用通知后，也会将提议应用到其状态机中，从而确保所有节点的状态一致。

四、举例说明
假设我们有一个分布式系统，由10个节点组成：P1、P2是提议者（Proposer），A1、A2、A3、A4、A5是接受者（Acceptor），L1、L2、L3是学习者（Learner）。

1、初始化阶段
在Multi-Paxos中，任何提议者都可以被选为领导者。
系统启动时，通过某种机制（比如Paxos算法）选举出一个新的领导者，这里假设P1被选为领导者。

2、准备阶段（Prepare Phase）
领导者P1，生成一个提议编号（例如7），向所有接受者询问，是否可以接受编号为7的提议。
接受者A1~A5收到消息后，由于提议编号7大于它们之前见过的任何提议编号，将进入承诺状态，并向P1发送可接受提议编号7的提议，并承诺不会接受任何编号小于7的提议。
【通过算法优化，其实可以节省提议编号这个阶段，直接发起提议】

3、接受阶段（Accept Phase）
当受到大多数接受者同意提议编号的消息后，P1向集群中的所有接受者发送Accept消息，提议编号7的内容为V7。
接收者收提议后，如果该提议编号高于它们当前已接受的提议，则会接受该提议并返回确认消息。

4、提交阶段（Commit Phase）
一旦P1收到来自多数接受者的已接受消息，它将向所有接受者发送提交消息，指示它们可以提交这个提议。

5、应用阶段（Apply Phase）
接受者在收到提交消息后，将提议的键值对应用到状态机中，并将结果通知学习者。

五、与Paxos算法对比
并发性：Paxos算法在每次达成共识时都需要进行两轮消息传递，这限制了它的并发能力。而Multi-Paxos通过引入领导者（Leader）的概念，允许多个提议者并发地提出提议，从而提高了并发性。
消息复杂度：在Paxos算法中，每个提议都需要两轮的通信（Prepare和Accept阶段），这增加了消息的复杂度。Multi-Paxos通过减少通信轮次，允许领导者在一轮中提出多个提议，从而减少了消息的复杂度。
实时性：由于Multi-Paxos允许并发提议，它在实时性方面通常优于Paxos算法。在Paxos算法中，每个提议都需要等待前一个提议完成后才能开始，这可能导致延迟。
容错性：Paxos算法和Multi-Paxos都具有很好的容错性，但Multi-Paxos由于其并发性，在某些容错情况下可能表现更好，例如在领导者失败时可以快速选举新领导者并继续处理提议。
实现复杂度：Paxos算法的实现相对复杂，而Multi-Paxos虽然在理论上提供了并发性的优势，但其实现也引入了额外的复杂性，如领导者选举和故障恢复机制。
优化和变种：Multi-Paxos有许多优化和变种，如Fast Paxos和EPaxos，它们通过进一步减少通信轮次或利用特定的系统特性来提高性能。而在实际应用中，许多系统采用Multi-Paxos或其变种，如Raft算法，以提高性能。

分布式一致性算法01：Paxos

Posted on by — No Comments ↓

分布式一致性算法01 Paxos算法

一、基本概念
Paxos是分布式一致性的经典算法，由Leslie Lamport在1990年提出。

二、Paxos算法通常涉及三种角色：
Proposer（提议者） ：负责提出提议（Proposal），即向系统中提出一个值。Proposer通常是客户端，负责发起提议并分配一个不重复的自增ID给每个提议。
Acceptor（接受者） ：参与决策过程，负责接收并回应Proposer的提议。每个Acceptor只能接受一个值，并且为了保证最多只有一个值被选定（Chosen），Proposal必须被超过一半的Acceptors所接受。
Learner（学习者） ：负责学习最终被选定的值。Learner不参与协商过程，只是接收并记录最终被选定的值。
在实际过程中，一个节点可以同时承担1~3个角色。

三、Paxos算法的基本过程
1、准备阶段（Prepare Phase）：
提议者（Proposer）选择一个提议编号（ballot number），并将其发送给所有接受者（Acceptor）。
接受者在接收到提议者的准备请求后，如果当前编号大于其已承诺的最高编号，则更新其承诺编号，并返回一个承诺（promise）给提议者，承诺中包含当前已接受的最高编号和值。

2、提议阶段（Proposal Phase）：
提议者收集到多数接受者的承诺后，选择一个值（value），并结合最新的提议编号，生成提议（propose）消息发送给接受者。
接受者在接收到提议消息后，如果提议编号大于其已有的承诺编号，则接受该提议，并返回确认消息给提议者。

3、决定阶段（Decide Phase）：
提议者收集到多数接受者的确认消息后，可以决定该值为最终值，并将其写入日志或状态机中。
学习者（Learner）从提议者处获取并学习最终决定的值，确保所有节点都有一致的状态。

四、举例说明：
假设我们有一个分布式系统，包含10个节点：P1、P2是提议者，A1、A2、A3、A4、A5是接受者，L1、L2、L3是学习者。

1、准备阶段：
P1提出一个提议编号，编号为1。
P1向所有接受者A1~A5发送询问，询问P1将发起编号为1提议是否可以。
A1收到提议时，并没有反馈过任何一次提议，于是反馈可以接受，并承诺，后续不会接受编号比1小的提议。A2~A4类似。

几乎同时，P2提出一个提议，编号为5。
P2向所有接受者A1~A5发送询问，询问P2将发起编号为5提议是否可以。
A1收到提议时，承诺的最小编号为1，于是反馈可以接受，并承诺，后续不会接受编号比5小的提议。A2~A4类似。

到这里，P1和P2的提议，前后都被允许提交了。当然，也有情况可能是，部分节点先收到了P2，这种情况下，P1的提议编号就无效了，需要重新拟定编号，这个编号必须单调增加。

2、提议阶段
P1收到了过半节点的提议编号反馈，向所有接受者A1~A5发送提议，告知提议编号为1的提议值为V1。
接受者收到提交消息时，已经无法接收比5小的提议，于是就拒绝P1，提议不通过。

P2收到了过半节点的提议编号反馈，向所有接受者A1~A5发送提议，告知提议编号为5的提议值为V5。
接受者收到提交消息时，反馈P2同意了5号提议。

3、决定阶段
当提议5收到过半同意反馈时（5个节点中3个以上同意），认为提议通过，各节点并将V5写入日志。
此时，学习者L1、L2、L3也会学习到V5的结果，并写入日志。

五、Paxos算法的特点
多数同意：在Paxos算法中，只有当提议者收到超过半数接受者的同意时，提议才可能被提交。
唯一性：Paxos算法保证了在任何给定的一轮中，只有一个提议可以被接受。
容错性：即使在一些节点失败的情况下，Paxos算法也能够工作。
Paxos算法的实现和理解都相当复杂，但它是许多现代分布式系统一致性协议的基础，如Raft算法等。

编译guetzli

Posted on by — No Comments ↓ 
#1.下载并安装配置vcpkg
git clone https://github.com/microsoft/vcpkg.git
cd vcpkg
bootstrap-vcpkg.bat
vcpkg integrate install
vcpkg install libpng

# 如果用CMake，记录下面的输出路径
CMake projects should use:
"-DCMAKE_TOOLCHAIN_FILE=D:/Build/vcpkg/scripts/buildsystems/vcpkg.cmake"

#2.下载guetzli
git clone https://github.com/google/guetzli.git

#3.用VS2017进行编译

#4.测试效果
整体上压缩比率还是很不错的，但这个压缩速度，还是放弃吧。

Update:
如果是图像压缩的话，现在webp格式还是很不错的，可以直接下载工具：
https://developers.google.com/speed/webp/download
https://chromium.googlesource.com/webm/libwebp/

运煤问题

Posted on by — No Comments ↓

提问：
一个山西煤老板，在矿区开采了3000吨煤需要运送到市场上去卖，从矿区到市场有1000公里。现在有一列烧煤的火车，该火车最多只能装1000吨煤，但其每一公里需要耗一吨煤作为燃料。请问，怎么运送才能运最多的煤到集市？（火车可以调头，火车最终不需要返回煤矿）

约束：
1、火车一定需要调头
2、调头的原则是，消耗的燃料越少越好
3、当煤不足一车时，仍然要当作一车运输

解答：
1、当煤多于2000吨时，火车一定要运三次，同样的路要跑五次
1000吨煤，走五次，可以走1/5路程
2、当煤多余1000吨时，火车一定要运两次，同样的路要跑三次
1000吨煤，走三次，可以走1/3路程
3、最终剩余1000吨时，直接跑到终点
最后剩余路程为1-1/5-1/3=7/15
跑完后剩余的煤为1000-7/15*1000=1000*8/15=533零1/3吨

以上。

排序算法C Part01

Posted on by — No Comments ↓

1、冒泡排序

//冒泡排序BubbleSort
//每次扫描，比较和交换相邻元素，保证一次扫描后，最大元素在最后一个
//每次扫描后，扫描队列长度减一
//时间复杂度：O(N^2)
//空间复杂度：O(N)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void BubbleSort(int Q[], int N)
{
  int i;
  int swap=1;
  int Temp;
  
  while(swap>0)
    {
      swap=0;
      for(i=1;i<N;i++)
	{
	  if(Q[i-1]>Q[i])
	    {
	      swap++;
	      Temp=Q[i-1];
	      Q[i-1]=Q[i];
	      Q[i]=Temp;
	    }
	}
    }
}

2、选择排序

//选择排序SelectionSort
//从头扫描到尾，每次将最小元素放到第一个
//每次扫描后，队列长度减一
//时间复杂度：O(N^2)
//空间复杂度：O(N)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void SelectionSort(int Q[], int N)
{
  int i,j,k;
  int Temp;
  for(i=0;i<N;i++)
    {
      k=i;
      for(j=i+1;j<N;j++)
	{
	  if(Q[j]<Q[i])k=j;
	}  

      Temp=Q[k];
      Q[k]=Q[i];
      Q[i]=Temp;
    }
}

3、插入排序

//插入排序InsertionSort
//起始队列长度为1，每次队列长度加1
//通过元素移动，将队列调整为有序状态
//时间复杂度：O(N^2)
//空间复杂度：O(N)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void InsertionSort(int Q[], int N)
{
  int i,j;
  int Temp;
  for(i=1;i<N;i++)
    {
      Temp = Q[i];
      for(j=i;j>0 && Q[j-1]>Temp;j--)
	{
	  Q[j]=Q[j-1];
	}

      Q[j]=Temp;
    }
}

4、希尔排序

//希尔排序ShellSort
//指定一个步长，将需要排序的数字，按序号%步长分组
//对每组进行插入排序，然后减小步长，再次分组，排序直到步长为1结束
//时间复杂度：O(n^2)
//空间复杂度：O(n)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void ShellSort(int Q[], int N)
{
  int i,j;
  int Temp;
  int Step;

  for(Step=N/2;Step>0;Step=Step/2)
    {
      for(i=Step;i<N;i++)
	{
	  Temp = Q[i];
	  for(j=i;j>=Step && Q[j-Step]>Temp;j=j-Step)
	    {
	      Q[j]=Q[j-Step];
	    }
	  Q[j]=Temp;
	}
      //dumpArray(Q,N);
    }
}

5、归并排序

//归并排序MergeSort
//二路归并首先将归并长度定为2，在归并集内进行排序
//然后归并长度×2，将有序集合进行归并
//时间复杂度：O(NlogN)
//空间复杂度：O(N)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void Merge(int Q[],int TempArray[], int left, int mid, int right)
{
  int i=left,j=mid,k=left;

  while(i<mid && j<=right)
    {
      if(Q[i]>Q[j])
	{
	  TempArray[k++]=Q[j++];
	}
      else
	{
	  TempArray[k++]=Q[i++];
	}
    }

  while(i<mid)
    {
	  TempArray[k++]=Q[i++];
    }

  while(j<=right)
    {
      	  TempArray[k++]=Q[j++];
    }

  for(k=left;k<=right;k++)
    {
      Q[k]=TempArray[k];
    }

}

void MSort(int Q[],int TempArray[], int left, int right)
{
  int center;

  if(left<right)
    {
      center=(left+right)/2;
      MSort(Q,TempArray,left,center);
      MSort(Q,TempArray,center+1,right);
      Merge(Q,TempArray,left,center+1,right);
    }
}

void MergeSort(int Q[], int N)
{
  int *TempArray = malloc(N*sizeof(int));

  if(TempArray!=NULL)
    {
      MSort(Q,TempArray,0,N-1);
    }
  else
    {
      //Todo: deal with not enough memory
      //RaiseError("MergeSort: not enough memory");
    }
}

八后问题Ruby02

Posted on by — No Comments ↓

Queen.rb

class Queen
  
  def initialize()
    @v=0
  end
  
  def canSetQueen(lst,s,x,y)
      lstNo = Array.new()
    
      for i in 0..s-1 do
        p = Pt.new(x,i)
        lstNo.push(p)
      end
      
      for j in 0..s-1 do
        p = Pt.new(j,y)
        lstNo.push(p)
      end 
      
      x0=x
      y0=y
      while x0<s and y0<s
        p=Pt.new(x0,y0)
        lstNo.push(p)
        x0=x0+1
        y0=y0+1
      end
      
      x0=x
      y0=y
      while x0>=0 and y0>=0
        p=Pt.new(x0,y0)
        lstNo.push(p)
        x0=x0-1
        y0=y0-1
      end
      
      x0=x
      y0=y
      while x0>=0 and y0<s
        p=Pt.new(x0,y0)
        lstNo.push(p)
        x0=x0-1
        y0=y0+1
      end
      
      x0=x
      y0=y
      while x0<s and y0>=0
        p=Pt.new(x0,y0)
        lstNo.push(p)
        x0=x0+1
        y0=y0-1
      end
      
      while(lstNo.length>0)
        p=lstNo.pop
        if(p.y==lst[p.x])
          return false
        end
      end
      
      return true
  end
    
  def findQueen(lst,s,x) 
      
      if(x>=s)
        @v=@v+1
        puts("]>>solution No."+@v.to_s)
        pp lst
        return
      end
      
      for y in 0..s-1 do
        if(canSetQueen(lst,s,x,y))
          lst.push(y)   
          findQueen(lst,s,x+1)
          lst.pop
        end
      end
       
    end
end

class Pt
  attr_accessor:x
  attr_accessor:y
  def initialize(x,y)
      @x=x
      @y=y
  end
end

test.rb

require "pp"
require "./Queen.rb"

len = 8
lst = Array.new()

q=Queen1.new
q.findQueen(lst,len,0)

puts("end")

八后问题Ruby01

Posted on by — No Comments ↓

Queen.rb

class Queen
  
  def initialize()
    @v=0
  end
  
  def arrCopy2(arr)
    arr0=Array.new(arr.length)
    for i in 0..arr.length-1 do
      arr0[i]=Array.new(arr[i])
    end
    
    return arr0
  end
  
  def addQueen(arr,x,y)
    setQueen(arr,x,y,1)
  end
  
  def setQueen(arr,x,y,n)
    for i in 0..arr.length-1 do
      arr[x][i]=n
    end
    
    for j in 0..arr[x].length-1 do
      arr[j][y]=n
    end 
    
    x0=x
    y0=y
    while x0<arr.length and y0<arr&#91;x0&#93;.length
      arr&#91;x0&#93;&#91;y0&#93;=n
      x0=x0+1
      y0=y0+1
    end
    
    x0=x
    y0=y
    while x0>=0 and y0>=0
      arr[x0][y0]=n
      x0=x0-1
      y0=y0-1
    end
    
    x0=x
    y0=y
    while x0>=0 and y0<arr&#91;x0&#93;.length
      arr&#91;x0&#93;&#91;y0&#93;=n
      x0=x0-1
      y0=y0+1
    end
    
    x0=x
    y0=y
    while x0<arr.length and y0>=0
      arr[x0][y0]=n
      x0=x0+1
      y0=y0-1
    end
    
    return arr
  end
  
  def findQueen(arr,lst,x) 
    
    if(x>=arr.length)
      @v=@v+1
      puts("]>>solution No."+@v.to_s)
      pp lst
      return
    end
    
    for y in 0..arr[x].length-1 do
      if(arr[x][y]==0)
        lst.push(y)
        arr0=arrCopy2(arr)
        addQueen(arr,x,y)   
        findQueen(arr,lst,x+1)
        arr=arr0
        lst.pop
      end
    end
     
  end
  
end

test.rb

require "pp"
require "./Queen.rb"

len = 8
arr=Array.new(len){Array.new(len, 0)}
#fuck
#arr = Array.new(len, Array.new(len,0))

lst = Array.new()

q=Queen.new
q.findQueen(arr,lst,0)

puts("end")

二进制数字中1的个数

Posted on by — No Comments ↓ 
#include "stdafx.h"
#include <nmmintrin.h>

/*
 *通过移位计算1的个数
 *每一位都要判断和处理
 */
int BitCount(unsigned int n)
{
	unsigned int c = 0;
	while (n >0)
	{
		if ((n & 1) == 1)++c;
		n >>= 1;
	}
	return c;
}

/*
 *通过减法及位运算，保证每次至少消除一个1
 *只处理1的位，0的位不处理
 */
int BitCountWithMinus(unsigned int n)
{
	unsigned int c = 0;
	for (c = 0; n; ++c)
	{
		n &= (n - 1);
	}
	return c;
}

/*
*将32位数字，截为4个8位数
*通过查表，得到每个8位数中1的个数，然后求和
*/
int BitCountLUT8(unsigned int n)
{
	unsigned char BitsSetTable256[256] = { 0 };

	for (int i = 0; i <256; i++)
	{
		BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
	}

	unsigned int c = 0;

	unsigned char* p = (unsigned char*)&n;

	c = BitsSetTable256[p[0]] +
		BitsSetTable256[p[1]] +
		BitsSetTable256[p[2]] +
		BitsSetTable256[p[3]];

	return c;
}

/*
*将32位数字，截为4个8位数
*通过查表，得到每个8位数中1的个数，然后求和
*LUT表已经计算好
*/
int BitCountLUT8Static(unsigned int n)
{
	unsigned int table[256] =
	{
		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
	};

	return table[n & 0xff] +
		table[(n >> 8) & 0xff] +
		table[(n >> 16) & 0xff] +
		table[(n >> 24) & 0xff];
}

/*
*将32位数字，截为8个4位数
*通过查表，得到每个4位数中1的个数，然后求和
*LUT表已经计算好
*/
int BitCountLUT4Static(unsigned int n)
{
	unsigned int table[16] =
	{
		0, 1, 1, 2,
		1, 2, 2, 3,
		1, 2, 2, 3,
		2, 3, 3, 4
	};

	unsigned int count = 0;
	while (n)
	{
		count += table[n & 0xf];
		n >>= 4;
	}
	return count;
}

/*
*将32位数字，相邻的2位求和，然后相邻的4位求和
*然后相邻的8位、16位、32位求和
*/
int BitCountParallel(unsigned int n)
{
	n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
	n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
	n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
	n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
	n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);

	return n;
}

/*
*第一行，计算每三位的1的个数（其实11*3是33位，但最高一位可以假设为0，所以没问题）
*第二行，实际上是先计算了相邻6位中1的个数（不会产生进位，结果最多占到3位），并将前三位置为0
*然后通过取模，相当于将每6位数字做了加法
*/
int BitCountMagic(unsigned int n)
{
	unsigned int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
	return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

unsigned int n = 127;
unsigned int bitCount = _mm_popcnt_u32(n);


/*
*将8位数字，转换为MY_UNSIGHED_CHAR结构体，然后求和
*/
struct MY_UNSIGHED_CHAR
{
	unsigned a : 1;
	unsigned b : 1;
	unsigned c : 1;
	unsigned d : 1;
	unsigned e : 1;
	unsigned f : 1;
	unsigned g : 1;
	unsigned h : 1;
};

long BitCountStuct(unsigned char b)
{
	struct MY_UNSIGHED_CHAR *by = (struct MY_UNSIGHED_CHAR*)&b;
	return (by->a + by->b + by->c + by->d + by->e + by->f + by->g + by->h);
}

int _tmain(int argc, _TCHAR* argv[])
{
	printf("There are %d 1 in 133\n", BitCount(133));
	printf("There are %d 1 in 133\n", BitCountWithMinus(133));
	printf("There are %d 1 in 133\n", BitCountLUT8(133));
	printf("There are %d 1 in 133\n", BitCountLUT8Static(133));
	printf("There are %d 1 in 133\n", BitCountLUT4Static(133));
	printf("There are %d 1 in 133\n", BitCountParallel(133));
	printf("There are %d 1 in 133\n", BitCountMagic(133));
	printf("There are %d 1 in 133\n", BitCountStuct(133));
	return 0;
}

用位运算实现加减乘除

Posted on by — No Comments ↓ 
        //加法
	public static int add(int a, int b)  
	{  
	    int ans;  
	    while(b!=0)  
	    {
	        ans = a^b;
	        b = ((a&b)<<1);
	        a = ans;  
	    }  
	    return a;  
	}  
	
	//减法
	public static int sub(int a, int b)
	{  
	    return add(a, -b);  
	}
	
	//正数乘法
	private static int posMultiply(int a,int b)  
	{  
	    int ans = 0;  
	    while(b>0)  
	    {  
	        if((b&0x1)==1)ans = add(ans, a);  
	        a = (a<<1);  
	        b = (b>>1);  
	    }  
	    return ans;  
	}  
	  
	//乘法
	public static int multiply(int a,int b)  
	{  
	    if(a==0||b==0)return 0;  
	    if(a>0 && b>0)  
	        return posMultiply(a, b);  
	    if(a<0)  
	    {  
	        if(b<0)  
	        {  
	            return posMultiply(-a, -b);  
	        } 
	        else
	        {
	        	return -posMultiply(-a, b ); 
	        }
	    }
	    else
	    {
	    	return -posMultiply(a, -b);
	    }
	}  
	  
	//正数除法
	private static int posDiv(int x,int y)  
	{  
	    int ans=0;  
	    for(int i=31;i>=0;i--)  
	    {
	        if((x>>i)>=y)  
	        {  
	            ans+=(1<<i);  
	            x-=(y<<i);  
	        }  
	    }  
	    return ans;  
	}  
	  
	//除法
	public static int div( int a, int b )  
	{
		assert(b!=0);
	    if(a==0)return 0;

	    if(a>0)  
	    {  
	        if(b>0)
	        {
	            return posDiv(a,b); 
	        }
	        else
	        {
	        	return -posDiv( a,-b);  
	        }
	    }  
	    else
	    {
	    	if(b>0)
	    	{
		        return -posDiv(a, b);  
	    	}
	    	else
	    	{
	    		return -posDiv(-a, -b);  
	    	}
	    }
	    
	}   
	
	//求负数
	public static int negtive(int a)
	{  
	    return add(~a, 1);  
	}
	  
	//比较正数大小
	private static boolean isbigerPos( int a, int b )   
	{
	    int c = 1;  
	    b = (a^b);  
	    if(b==0)return false;
	    
	    while(b>0)  
	    {  
	    	b>>=1;
	        c <<= 1;  
	    }  
	    return (c&a)==0;  
	}   
	  
	//比较大小   
	public static boolean isbiger( int a, int b )   
	{
	    if(a<0)  
	    {  
	        if(b<0)  
	        {  
	            return isbigerPos( negtive(b), negtive(a) );  
	        }
	        else
	        {
	        	return false;  
	        }
	    }
	    else
	    {
		    if(b<0)
		    {
		        return true;  
		    }
		    else
		    {
		    	return isbigerPos(a, b);  
		    }
	    }

	}

	public static int divideby3(int x)  
	{  
	    int sum = 0;  
	    while(x > 3)  
	    {  
	        sum = add(x>>2 , sum);  
	        x = add(x>>2 , x&3);  
	    } 
	    if(x == 3) 
	    {
	        sum = add(sum , 1);
	    }
	    return sum;  
	}  
	
	public static void main(String[] args)
	{
		System.out.println(add(13,19));
		System.out.println(sub(13,19));
		System.out.println(multiply(13,19));
		System.out.println(div(10,5));
		System.out.println(negtive(13));
		System.out.println(isbiger(10,5));
		System.out.println(isbiger(10,11));
		
		System.out.println(divideby3(15));
		System.out.println(divideby3(14));
		System.out.println(divideby3(13));
		System.out.println(divideby3(12));
		System.out.println(divideby3(11));
	}