如何判断一个数是一个完全平方数，写出你认为比较高效的算法。
[问题点数：20分，结帖人kevin820601]
如何判断一个数是一个完全平方数，写出你认为比较高效的算法。
[问题点数：20分，结帖人kevin820601]
只显示楼主
取消只显示楼主
匿名用户不能发表回复！|用位运算实现四则运算之加减乘除（用位运算求一个数的1/3） via Hackbuteer1 - scott_h - 博客园
随笔 - 219, 文章 - 0, 评论 - 0, 引用 - 0
^: 按位异或；&：按位与； | ：按位或
计算机系统中，数值一律用补码来表示：因为补码可以使符号位和数值位统一处理，同时可以使减法按照加法来处理。
对补码做简单介绍：数值编码分为原码，反码，补码，符号位均为0正1负。
原码 -& 补码： 数值位取反加1
补码 -& 原码： 对该补码的数值位继续 取反加1
补码 的绝对值（称为真值）：正数的真值就是本身，负数的真值是各位（包括符号位）取反加1（即变成原码并把符号位取反）.
b -& -b ： 各位（包括符号位）取反加1
加法运算：将一个整数用二进制表示，其加法运算就是：相异（^）时，本位为1，进位为0；同为1时本位为0，进位为1；同为0时，本位进位均为0.
所以，不计进位的和为sum = a^b，进位就是arr = a&b,(与sum相加时先左移一位，因为这是进位）。完成加法直到进位为0.
减法运算：a-b = a+(-b)　　根据补码的特性，各位取反加1即可（注意得到的是相反数，不是该数的补码，因为符号位改变了）
（上面用二进制实现的加减法可以直接应用于负数）
乘法运算：原理上还是通过加法计算。将b个a相加，注意下面实际的代码。
除法运算：除法运算是乘法的逆。看a最多能减去多少个b，
加法运算：
int AddWithoutArithmetic(int num1,int num2)
if(num2==0) return num1;//没有进位的时候完成运算
sum=num1^num2;//完成第一步没有进位的加法运算
carry=(num1&num2)&&1;//完成第二步进位并且左移运算
return AddWithoutArithmetic(sum,carry);//进行递归，相加
//简化一下：
int Add(int a,int b)
return b ? Add(a^b,(a&b)&&1) :
return Add(a^b,(a&b)&&1);
//上面的思路就是先不计进位相加，然后再与进位相加，随着递归，进位会变为0，递归结束。
非递归的版本如下：
int Add(int a, int b)
//直到没有进位
ans = a^b;
//不带进位加法
b = ((a&b)&&1);
减法运算：
//这个和加法一样了，首先取减数的补码，然后相加。
int negtive(int a)
return Add(~a, 1);
int Sub(int a, int b)
return Add(a, negtive(b));
正数乘法运算：
//正数乘法运算
int Pos_Multiply(int a,int b)
int ans = 0;
ans = Add(ans, a);
a = (a&&1);
b = (b&&1);
整数除法（正整数）
//除法就是由乘法的过程逆推，依次减掉（如果x够减的）y^(2^31),y^(2^30),...y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。
int Pos_Div(int x,int y)
int ans=0;
for(int i=31;i&=0;i--)
//比较x是否大于y的(1&&i)次方，避免将x与(y&&i)比较，因为不确定y的(1&&i)次方是否溢出
if((x&&i)&=y)
ans+=(1&&i);
x-=(y&&i);
// 加减乘除位运算
// 程序中实现了比较大小、加减乘除运算。所有运算都用位操作实现
// 在实现除法运算时，用了从高位到低位的减法
// 具体如下，算法也比较简单，所以没有作注释
#include&iostream&
#include&cstdio&
using namespace
int Add(int a, int b)
//直到没有进位
ans = a^b;
//不带进位加法
b = ((a&b)&&1);
//这个和加法一样了，首先取减数的补码，然后相加。
int negtive(int a)
return Add(~a, 1);
int Sub(int a, int b)
return Add(a, negtive(b));
// 判断正负
int ispos( int a )
return (a&0xFFFF) && !(a&0x8000);
int isneg( int a )
return a&0x8000;
int iszero( int a )
return !(a&0xFFFF);
//正数乘法运算
int Pos_Multiply(int a,int b)
int ans = 0;
ans = Add(ans, a);
a = (a&&1);
b = (b&&1);
//乘法运算
int Multiply(int a,int b)
if( iszero(a) || iszero(b) )
if( ispos(a) && ispos(b) )
return Pos_Multiply(a, b);
if( isneg(a) )
if( isneg(b) )
return Pos_Multiply( negtive(a), negtive(b) );
return negtive( Pos_Multiply( negtive(a), b ) );
return negtive( Pos_Multiply(a, negtive(b)) );
//除法就是由乘法的过程逆推，依次减掉（如果x够减的）y^(2^31),y^(2^30),...y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。
int Pos_Div(int x,int y)
int ans=0;
for(int i=31;i&=0;i--)
//比较x是否大于y的(1&&i)次方，避免将x与(y&&i)比较，因为不确定y的(1&&i)次方是否溢出
if((x&&i)&=y)
ans+=(1&&i);
x-=(y&&i);
//除法运算
int MyDiv( int a, int b )
if( iszero(b) )
cout && "Error" &&
if( iszero(a) )
if( ispos(a) )
if( ispos(b) )
return Pos_Div(a, b);
return negtive( Pos_Div( a, negtive(b)) );
if( ispos(b) )
return negtive( Pos_Div( negtive(a), b ) );
return Pos_Div( negtive(a), negtive(b) );
// 比较两个正数的大小（非负也可）
int isbig_pos( int a, int b )
int c = 1;
b = (a^b);
if( iszero(b) )
while( b &&= 1 )
return (c&a);
// 比较两个数的大小
int isbig( int a, int b )
if( isneg(a) )
if( isneg(b) )
return isbig_pos( negtive(b), negtive(a) );
if( isneg(b) )
return isbig_pos(a, b);57. 三数之和、58. 四数之和（双指针）
给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。 注意事项在三元组(a, b, c)，要求a &= b &= c。结果不能包含重复的三元组。样例如S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是：(-1, 0, 1)(-1, -1, 2)思想：类似两数之和，两个指针关键：如何处理重复三元组代码：class Solution {
* @param numbers: Give an array numbers of n integer
* @return: Find all unique triplets in the array which gives the sum of zero.
vector&vector&int&& threeSum(vector&int& &nums) {
// write your code here
vector&vector&int& &
sort(nums.begin(), nums.end());//vector调用sort函数，参数为迭代器
for (int i = 0; i & nums.size(); i++)
if (i & 0 && nums[i] == nums[i - 1])
//if语句的作用是防止重复三元组，下同
int start = i + 1, end = nums.size() - 1;
int target = -nums[i];
while (start & end)
if (start & i + 1 && nums[start - 1] == nums[start])
if (nums[start] + nums[end] & target)
} else if (nums[start] + nums[end] & target)
vector&int&
triple.push_back(nums[i]);
triple.push_back(nums[start]);
triple.push_back(nums[end]);
result.push_back(triple);
};若去掉上述带continue的if语句，会出现如下情况解法二（时间复杂度高）解题思路:直接三重循环求解，用set去除重复的组合。算法如下:
vector&vector&int& & threeSum(vector&int& &nums) {
vector&vector&int& &
set&vector&int& &
sort(nums.begin(), nums.end());
int size = nums.size();
for (int i = 0; i & size && nums[i] &= 0; i++) {
for (int j = i + 1; j & j++) {
for (int k = j + 1; k & k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
vector&int& tempV
tempVec.push_back(nums[i]);
tempVec.push_back(nums[j]);
tempVec.push_back(nums[k]);
s.insert(tempVec);//set键是唯一的，不能存储多个相同的值
set&vector&int& &::
for (it = s.begin(); it != s.end(); it++) {
vec.push_back(*it);//将s中的数据，置换到vec中
}58、四数之和给一个包含n个数的整数数组S，在S中找到所有使得和为给定整数target的四元组(a, b, c, d)。样例例如，对于给定的整数数组S=[1, 0, -1, 0, -2, 2] 和 target=0. 满足要求的四元组集合为：(-1, 0, 0, 1)(-2, -1, 1, 2)(-2, 0, 0, 2)思想：与三数之和完全相似class Solution {
* @param numbers: Give an array
* @param target: An integer
* @return: Find all unique quadruplets in the array which gives the sum of zero
vector&vector&int&& fourSum(vector&int& nums, int target) {
// write your code here
int n=nums.size();
vector&vector&int&&
sort(nums.begin(),nums.end());
for(int i=0;i&n;i++)
if(i&0&&nums[i]==nums[i-1])
int target1=target-nums[i];
int start1=i+1,end1=n-1;
for(;start1&end1;start1++)
if(start1&i+1&&nums[start1]==nums[start1-1])
int target2=target1-nums[start1];
int start2=start1+1,end2=end1;//不要写成end2=end1-1;否则会出下图错误
while(start2&end2)
if(start2&start1+1&&nums[start2]==nums[start2-1])
{start2++;}
if(nums[start2]+nums[end2]&target2)
else if(nums[start2]+nums[end2]&target2)
vector&int&
trip.push_back(nums[i]);
trip.push_back(nums[start1]);
trip.push_back(nums[start2]);
trip.push_back(nums[end2]);
result.push_back(trip);
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！Python基本数据类型
字符串：引号，成对出现，不能混搭。可为单引号，双引号，三个引号。
name = "我是对方正在输入"
name = 'alex'
name="""哈哈哈哈哈"""
name='''这样的引号也可以''''加法：
n3='''对方正在输入'''
n4=n1+n2+n3乘法：
n1="""乘法的话字符串时重复出现多少遍"""
n2=n1*10数字：
加减乘除幂次方：
#-------&取余数，小数点后
#--------&取真实的商，小数点前及小数点后都取
#-------&取整数商，小数点前应用举例：判断13是偶数还是基数a = 13
if a % 2 == 0 :
print("a是偶数")
print("a是基数")
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！csdn 写博客体验越来越差了。。。。。。
Fib数通项公式
求某个数的前4位
Time Limit:
MS (Java/Others)
Memory Limit:
K (Java/Others)
Total Submission(s): 2076
Accepted Submission(s): 959Problem Description
2007年到来了。经过2006年一年的修炼，数学神童zouyu终于把0到的Fibonacci数列
(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i&=2))的值全部给背了下来。
接下来，CodeStar决定要考考他，于是每问他一个数字，他就要把答案说出来，不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了，可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。
输入若干数字n(0 &= n &= )，每个数字一行。读到文件尾。
输出f[n]的前4个数字（若不足4个数字，就全部输出）。
Sample Input
Sample Output
首先必须知道
fib那次数列的通项公式 为
之后要知道
对数的性质,loga(b^c)=c*loga(b),loga(b*c)=loga(b)+loga(c);
假设给出,那么
log10()=log10(1.^7)=log10(1.;
log10(1.0234432)就是log10()的小数部分.
10^0..先取对数(对10取),然后得到结果的小数部分bit,
pow(10.0,bit)以后
如果答案还是&1000
那么就一直乘10。
#include&stdio.h&
#include&string.h&
#include&math.h&
int a[25];
int main()
a[0]=0;a[1]=1;
for(i=2;i&21;i++)
a[i]=a[i-1]+a[i-2];
while(scanf("%d",&n)!=EOF)
printf("%d\n",a[n]);
num=-0.5*log(5.0)/log(10.0)+((double)n)*log((sqrt(5.0)+1.0)/2.0)/log(10.0);
num-=int(num);
num=pow(10.0,num);
while(num&1000)
printf("%d\n",(int)num);
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！