Integer中用到了很多位运算,而java整数的固定长度也为位运算提供不少便利性,下面对Integer中的经典方法做分析(这些方法基本上都用到了位运算,原因很简单:高效,并行)
1.求整数中二进制1的个数
public static intbitCount(int i) {
// HD, Figure 5-2
i= i - ((i >>> 1) & 0x55555555);
i= (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i= (i + (i >>> 4)) & 0x0f0f0f0f;
i= i + (i >>> 8);
i= i + (i >>> 16);
returni & 0x3f;
}
分析:该方法仅需五步完成,时间复杂度是O(logN)(N是整数的二进制长度),算法妙在二进制并行运算,之后的算法很多也用到了并行运算。
分解:
第一步:求每两位中1的个数之和,比如i=(01)( 11)( 00)( 10)( 11)( 01)( 11)(01)->(01)(10)(00)(01)(10)(01)(10)(01)
第二步:求前面结果的每四位之和(0110)(0001)(1001)(1001)->(0010)(0001)(0010)(0010)
第三步:同上道理,求每8位置和
。。。。
并行:比如求没两位之和时,不用先等前面两位算完再算后面两位,直接同时进行,这也是位运算一大特色
2.返回具有至多单个1 位的 int 值,在指定的 int 值中最高位(最左边)的 1 位的位置
public static inthighestOneBit(int i) {
// HD, Figure 3-1
i |= (i >>
1);
i |= (i >>
2);
i |= (i >>
4);
i |= (i >>
8);
i |= (i >> 16);
return i - (i >>> 1);
}
分析:该方法时间复杂度是O(logN)
分解:
第一步:让整数二进制最高位为1的右边一位也为1
第二步:让整数二进制最高位为1的右边3位也为1
第三步:让整数二进制最高位为1的右边7位也为1
。。。。
最后整数二进制最高位为1的右边全为1,然后通过运算只保留最高位的1
3.返回具有至多单个 1 位的 int 值,在指定的 int 值中最低位(最右边)的 1位的位置
public static intlowestOneBit(int i) {
// HD, Section 2-1
return i & -i;
}
分析:该方法一步完成,妙哉!
4.在指定 int 值的二进制补码表示形式中最高位(最左边)的 1 位之前,返回零位的数量
public static intnumberOfLeadingZeros(int i) {
// HD, Figure 5-6
if (i == 0)
return 32;
int n = 1;
if (i >>> 16 == 0) { n += 16;i <<= 16; }
if (i >>> 24 == 0) { n +=
8; i <<= 8; }
if (i >>> 28 == 0) { n +=
4; i <<= 4; }
if (i >>> 30 == 0) { n +=
2; i <<= 2; }
n -= i >>> 31;
return n;
}
分析:时间复杂度是O(logN),采用了类似二分查找的思想
5.返回指定的 int 值的二进制补码表示形式中最低(“最右”)的为 1 的位后面的零位个数
public static intnumberOfTrailingZeros(int i) {
// HD, Figure 5-14
inty;
if(i == 0) return 32;
intn = 31;
y= i <<16; if (y != 0) { n = n -16; i = y; }
y= i << 8; if (y != 0) { n = n - 8; i = y; }
y= i << 4; if (y != 0) { n = n - 4; i = y; }
y= i << 2; if (y != 0) { n = n - 2; i = y; }
returnn - ((i << 1) >>> 31);
}
分析:类似上一方法
6.反转二进制整数
public static intreverse(int i) {
// HD, Figure 7-1
i= (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
i= (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
i= (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
i= (i << 24) | ((i & 0xff00) << 8) |
((i >>> 8) & 0xff00) | (i>>> 24);
returni;
}
分析:时间复杂度是O(logN),采用分治法,先局部后整体
分解:第一步:每相邻两位互换
第二步:每相邻四位互换,四位内部不互换
…..
7.获得整数征服符号表示:1,0,-1
public static intsignum(int i) {
// HD, Section 2-7
return (i >> 31) | (-i>>> 31);
}
分享到:
相关推荐
port: integer): integer;, 如果有绑定端口,下次软件先启动机器后启动也一样可以用 如果没绑定端口,必须保证机器先启动,软件后启动 3、设置服务器function JX102R_Set_Server(Ip: pchar; Port: integer = ...
功能相对完整的大整数类:Integer.使用VC++2008编写。较好地支持了无限长大整数乘、除、加、减、取模、移位、比较运算。可以于信息安全的加密算法中。算法效率较高。由于类中使用了运算符重载,功能强大,并且易于...
function SelectLocatPage(PageNum:integer):Range; //选择指定页面,返回选择范围 function GotoLocatPage(i:integer):Range; //移动到指定页面 返回一个范围 function getPageSize:Integer; //取得所有页码 ...
NoCases : integer);procedure PcntCorrect(VAR Xstr : array of string; NoCases : integer);procedure Percentiles(VAR Xstr : array of string; NoCases : integer);procedure zScores(VAR Xstr : array of ...
javaInteger⼤数据运算 ⼤数据运算 package com.oracle.demo01; import java.math.BigDecimal; import java.math.BigInteger; public class DemoInteger{ public static void main(String[] args) { //四则运算:...
FLetterKeyWidth: Integer; //字母按键宽度 FLetterKeyHeight: Integer; //字母按键高度 FNumberKeyWidth: Integer; //数字按键宽度 FNumberKeyHeight: Integer; //数字按键高度 FShiftKeyWidth: Integer;...
/此公用文件主要是对考勤机操作, 如果对收费机操作则可参考此文件定义结构即可. unit uPublic; interface Uses Windows , SysUtils , QForms , StdCtrls ,... function GetSizeOfData(pCommand: Pointer): Integer...
一个Delphi支持多线程的断点续传下载模块源码,可用在Delphi下载程序中,部分参数设置: dtAddTime : TDateTime; //发布时间 sResTitle : string; //资源名称 sDownloadURL, sSavedPath : string; //下载及...
property ProgressPostion:Integer read FProgressPostion write SetProgressPostion; end; var FrmProgress: TFrmProgress; implementation {$R *.dfm} procedure TFrmProgress.FormShow(Sender: TObject); ...
Design and write a Java class named SalesArray.java that will: 1. Declare a two-dimensional integer array named sales. Populate the first four columns using the following data. Quarter 1 Quarter 2 ...
constant h_data: integer:=640; constant h_front: integer:=16; constant h_back: integer:=48; constant h_sync: integer:=96; constant h_period: integer:= h_sync + h_data + h_front + h_back; -- ...
import java.io.*; public class Book{ double sb; double xb; Book(double x,double y){ this.sb=x; this.xb=y; } Book(){ } public static void main(String args[]){ System.out.println("请...
JAVA-int和Integer的区别1.zip
有如下关系模式,分析每个关系模式的主码,外码,完成后面的查询 职员表:Emp(eid:integer;ename:string,salary:real) 部门表:Dept(did:integer,dname:string,managerid:integer,floornum:integer) 职员与部分的...
Color: Integer; // 先前颜色 Speed: Integer; // 下落速率 nMove: Integer; // 下落距离 Stick: Integer; // '粘连'度 SnowNodes: array[0..SnowNumber] of SnowNode; // 雪点数组 hTimer: ...
对JAVA中的int类型和integer类型进行透彻分析的一个文档 很有帮助的哦 亲!
HugeInteger.java
var Mobile_Type,CopyRightToCOM:PChar):integer;stdcall;external 'sms.dll'; function Sms_Send(Sms_TelNum:string;Sms_Text:string):integer;stdcall;external 'sms.dll'; Function Sms_Receive(Sms_Type:...
function GetDelivery2(const recId: string): Integer;function GetDelivery(const recId: Int64): Integer;function GetInboxCount(const username: string; const password: string; const isRead: Boolean): ...
var V1:OleVariant):Integer; function ExecSQLStr(const SqlStr:string):Integer; //返回单表数据集 function GetSimpleData(const SqlStr:string;var V1:OleVariant):Integer; //主从巢状 function ...