久久无码人妻一区二区三区,欧美亚洲日本久久精品,久久久久久国产精品无码下载

flyinghearts — Sun, 15 Jun 2014 02:55:00 GMT

　　
　　Borland的那个恶心的SEH异常处理专利�Q�No:5,628,016 Filed: June, 15, 1997�Q�，�l�于到期了。希望GCC/CLANG能快点完成win32的C++异常的SEH实现�Q�下一版本的GCC�Q�能让用户不再纠�l�SJLJ�Q�Dwarf2的选择�?br />

flyinghearts 2014-06-15 10:55 发表评论

flyinghearts — Thu, 21 Mar 2013 14:00:00 GMT

题目�Q�数�l�中有三个数只出��C��ơ，其它的数恰好出现两次�Q�找��三个数�?/span>

先考虑“只有两个数出��C��?#8221;的情况：可以扑ֈ�一�U�方法，��数�l�划分�ؓ两部分，且让�q�两个数分别在不同部分，�q�样每部分所有数的异或��|��恰好分别�{�于�q�两个数。一�U�简单的分法��是�Q�先计算��两个数的异或�?/span>M�Q�等价于求数�l�中所有数的异或��|��Q�求�?/span>M值的二进制表�C�Z��的最低位1�Q�其它位�?/span>1也可以，只不�q�麻烦点�Q�在 +k位，然后�Ҏ�� +k位是否�ؓ1�Q�将原数�l�分��Z��部分�?/span>

回到原题�Q�假设这三个不同的数是：A�?/span>B�?/span>C�Q�它们的异或�?/span> X = A xor B xor C�Q?/span>X值可能�ؓ0�Q�也可能不�ؓ0。当X��g��?/span>0�Ӟ��比如�Q�这三个��Cؓ3�?/span>5�?/span>7�Q?/span>X��gؓ1�Q�，很难扑ֈ�一�U�方法，��原来的数组划分��Z��部分�Q��得这三个��C��都在同一部分。因而，要先对原来的数组�q�行一�ơ替换：��每个数�?/strong>X�q�行异或。这样原来的三个数就变成了：

B xor C�?/span>A xor C�?/span>A xor B。记a = B xor C�?/span>b = A xor C�?/span>c = A xor B。新的异或�?/span> x = a xor b xor c = 0�?/span>



    �׃��A�?/span>B�?/span>C互不相等�Q�显然它们间的异或�?/span>a�?/span>b�?/span>c都不�?/span>0�Q�且互不相等。（�?/span>a�{�于b�Q�则 0 = a xor b = (B xor C) xor (A xor C) = A xor B != 0自相矛盾�Q?/span>



若三个数的异或��gؓ0�Q�且其中一个数�?/span> +n位（n��Z�Q意��|��上�ؓ1�Q�则另两个数�?/span> +n位上必然一个�ؓ1�Q�另一个�ؓ0�Q�不然的话，�q�三个数的异或值就不会�?/span>0�Q�，因而根�?/span> +n位�ؓ1�Q�可以将�q�三个数分成两部�?/span>�?/span>

�?/span>f(x)�?/span>x的二�q�制表示中最低位1的位�|�，�?/span>f(a)�?/span>f(b)�?/span>f(c)�q�三个数中有且只有两个数相等。证明：不妨�?/span>f(a)�?/span>f(b)�?/span>f(c)中最��的�?/span>f(a)�Q?/span>k = f(a)�Q�则b�?/span>c�?/span> +k位上必然是一个�ؓ1�Q�一个�ؓ0�Q�不妨设b�?/span> +k位�ؓ1�Q�则�Ҏ��f(x)的定义以�?/span>f(a)最��，可得f(b)�{�于f(a)�Q?/span>f(c)大于f(a)。因而，新数�l�的�?/span>x对应的所�?/span>f(x)的��d��或值等�?/span>f(c)�?/span>

假设f(a)�{�于f(b)�Q?/span>m = f(c)�Q�由�?/span>c�?/span> +m位上�?/span>1�Q�不妨设 b�?/span> +m位也�?/span>1�Q�则a�?/span> +m位�ؓ0。根�?/span> +m位是否�ؓ1�Q�可��新数组分�ؓ两部分，每部分的异或值恰好都�?/span> a = B xor C�Q�可以求出数A�Q�等�?/span>a xor X�Q��?/span> ��数A攑օ�原来的数�l�，问题转�ؓ“只有两个数出��C��?#8221;的情况，利用前面提到的方法算出另两个数。��d��需遍历数组4�ơ�?/span>

代码�Q?/span>

#include

#include

static inline int extract_rightmost_one(unsigned value) { return value & -value; }

// if a != b, m = extract_rightmost_one(a), n = extract_rightmost_one(b),

//             k = extract_rightmost_one(a ^ b)

// then m == n != k   or   m == k != n   or n == k != m

void print_three_unique_number(const int arr[], unsigned len)

{

assert (len >= 3 && len % 2);

const int* const beg = arr;

const int* const end = arr + len;

int xor3 = 0;

for (const int* p = beg; p != end; ++p) xor3 ^= *p;

int flag1 = 0;

for (const int* p = beg; p != end; ++p) flag1 ^= extract_rightmost_one(*p ^ xor3);

assert(flag1 != 0 && (flag1 & (flag1 - 1u)) == 0u); // flag1 == 2^^k

int xor2 = 0;

for (const int* p = beg; p != end; ++p) {

    const int value = *p ^ xor3;

    if (value & flag1) xor2 ^= value; //or:

    // if ((value & flag1) == 0) xor2 ^= value;

}

const int number1 = xor2 ^ xor3;

const int flag2 = extract_rightmost_one(xor2);

int number2 = (number1 & flag2) ? number1 : 0; // put number1 into the array

for (const int* p = beg; p != end; ++p) {

    if (*p & flag2) number2 ^= *p;

}

const int number3 = xor2 ^ number2;

printf("%d %d %d\n", number1, number2, number3);

}

上面的代码�ƈ不严格符�?/span>C++标准�Q�而是假定机器采用补码表示负数�Q�不采用补码表示的老古董，一般�h也碰不到�Q��?/span> 另外要特别注意的是，一些计��最好先转�ؓ无符��h��Q�避免溢出，最后再转回有符��h��。因为标准假定有�W�号数间的计��不发生溢出�Q�当实际上发生溢出时�Q�就�?/span>UB行�ؓ�Q�编译器若进行些�Ȁ�q�的优化��得不到正确�l�果�?/span>

flyinghearts 2013-03-21 22:00 发表评论

mingw gcc的头文�g存在�l�构定义错误�Q�！

flyinghearts — Thu, 21 Mar 2013 13:51:00 GMT

准确的讲是mingw所用的sdk —— w32api�Q�存在结构定义错误�?br />
打开wingdi.h 定位�?tagGCP_RESULTSW 的结构定义位�|�，

typedef struct tagGCP_RESULTSW {
    DWORD lStructSize;
    LPWSTR lpOutString;
    UINT *lpOrder;
    int *lpDx;
    int *lpCaretPos;
    LPWSTR lpClass;         //正确的类型应该是 LPSTR
    LPWSTR lpGlyphs;
    UINT nGlyphs;
    int nMaxFit;
} GCP_RESULTSW,*LPGCP_RESULTSW;

�Ҏ��msdn, lpClass的类型应该是 LPSTR�Q?w32api却将其声明�ؓ LPWSTR�?br />
�q�个bug�Q�在2011�q�就有�h报告了，据说cvs版本也修正了�Q�但是直到现在，官方下蝲�q�是2011�q�发布的那个有bug的版本（w32api-3.17-2-mingw32-dev.tar.lzma�Q��?br />
另外�Q�mingw-w64�Q�支持生�?2位�?4位程序）不存在这个问题�?

flyinghearts 2013-03-21 21:51 发表评论

c++11 最反直觉的地方

flyinghearts — Thu, 22 Nov 2012 11:49:00 GMT

1 auto 会自动把引用去除�?br />
int& get();
auto k = get();     // k的类型是int�Q�而不是int&

Derived object;
auto&    same_object = (Base&)object;
auto another_object = (Base&)object; //会重新构造个Base对象


2 decltype 有时会自动把引用加上

int x;
decltype((x)) �?decltype(*&x) 的类型是int&�Q�而不是int

在宏中��用decltype�Ӟ��要特别注意别多加了括受��?br />
下面�q�段代码错在哪里�Q?br />    template
    auto min(T t, R r) -> decltype(t < r ? t : r)
    {
      return (t < r ? t : r);
    }

decltype(t < r ? t : r)的类型是T&或R&�Q�而不是所希望的T或R�Q?br />

标准是这栯��定的�Q?br />
The type denoted by decltype(e) is defined as follows:
— if e is an unparenthesized id-expression or an unparenthesized class member
     access (5.2.5), decltype(e) is the type of the entity named by e. If there
     is no such entity, or if e names a set of overloaded functions, the program
     is ill-formed;
— otherwise, if e is an xvalue, decltype(e) is T&&, where T is the type of e;
— otherwise, if e is an lvalue, decltype(e) is T&, where T is the type of e;
— otherwise, decltype(e) is the type of e.

3 std::move、std::forward、右值引�?br />
C++11 引入叛_��引用，可以做到�Q�函数�{发、针对��时对象优�?br /> move是动词，从字面上理解好像是要�U�d��对象�Q�其实std::move只是��单的��类型�{成右值引用而已�Q�！�Q?可以理解�?cast_to_rvalue_reference �?treat_as_temporal_object�?br />

void test1(int&&) {}

void test2(int&& value) //注意�Q�value的类型是int�Q�而不是int&&
{
     test1(value);    //无法�~�译通过�Q�因为value的类型是int�Q?必须转换�c�d��
     test1(static_cast(value));      //或�?br />     test1(std::forward(value));
}

test2函数中，value的类型是int�Q�而不是int&&�?br /> �q�是一个不得已的选择。如果value的类型是int&&的话�Q�就会有副作用：

void increase(int& value) { ++value; }
void test3(int&& value) { increase(value); }

char ch = 'a';
test3(ch); //本意是改变ch��|��但实际上ch��g��会改变，改变的是临时对像
通过转发函数test3�Q�increase函数可以修改临时对像�Q?br /> �q�造成�E�序员犯的错误（如上面的例子�Q�，难以在编译时��p��扑և�来�?br />

std::forward(value) �{��h�?static_cast(value)�Q�感觉后者更�Ҏ��理解�?br /> std::forward 起到的�{发作用。如果T�c�d��?R&�?R&&�Q�经�q�类型�{换后�Q�其�c�d��q�是和原来的一栗��?br /> 在C++11�?
    R& &   �{�同�?R&   �Q�在c++03中，R& &�q�种写法是非法的�Q?br />    R&& &   �{�同�?R&
    R& && �{�同�?R&
    R&& && �{�同�?R&&

flyinghearts 2012-11-22 19:49 发表评论

flyinghearts — Tue, 14 Aug 2012 13:19:00 GMT
int x;
decltype(x) �?nbsp; decltype((x)) 的类型是不一��L��?/div>
decltype(x) �?nbsp; decltype(*&x)   的类型是不一��L��?br />

decltype(x)的类型是 int
decltype((x)) �?decltype(*&x) 的类型是 int&

C++11标准�Q?/div>
The type denoted by decltype(e) is defined as follows:
— if e is an unparenthesized id-expression or an unparenthesized class member
     access (5.2.5), decltype(e) is the type of the entity named by e. If there
     is no such entity, or if e names a set of overloaded functions, the program
     is ill-formed;
— otherwise, if e is an xvalue, decltype(e) is T&&, where T is the type of e;
— otherwise, if e is an lvalue, decltype(e) is T&, where T is the type of e;
— otherwise, decltype(e) is the type of e.

flyinghearts 2012-08-14 21:19 发表评论

flyinghearts — Sun, 05 Aug 2012 13:02:00 GMT
弄着玩的。功能是��单的实现函数转发�Q�即
      调用CALL(func)�Q��{��用func()�Q?div>      调用CALL(func, arg1, arg2) �Q��{��用func(arg1, arg2)
代码中，宏CALL/STDCALL分别用来调用 __cdecl/__stdcall 调用规定的函�?br />             unsafe_call 两者都可调用，但它不是多线�E�安全的�?br />
代码只支持x86 32位，除内嵌汇�~�部分，��量�W�合C++11标准�?br />
原理�Q?br />     刚进入函数时�Q?br />     [esp]           函数�q�回地址
     [esp + 4]     �W�一个参敎ͼ�卌��{发函数的地址
     [esp + 8]     �W�二个参敎ͼ�卌��{发函数的的第一个参�?/div>    ...

      只要写三行汇�~�指令实��C��个c_call函数�Q�就可调用�{发函�?br />
      pop eax                             ; eax为函数返回地址
      xchg dword ptr[esp], eax     ; eax��{发函数的地址�Q�[esp]为函数返回地址
      jmp eax

     当�{发函数是__cdecl�Q�即转发函数不会调节栈，�׃��在c_call�Q�pop eax�Q��esp多加�?�Q�因而在调用完c_call后应该手动将esp值减4�Q�保证栈�q��?br />
    当�{发函数是__stdcall�Q��{发函��C��调节栈，调用转发函数完毕后，栈已�l�保持��^衡，因而调用c_call完毕�Q�不应该�q�行栈指针调节。似乎将c_call的调用改为__stdcall卛_��Q�但实际上c_call有变长参敎ͼ��Ҏ��__stdcall没效果，每次调用�~�译器还是会自动生成调节栈指针代码。因而只能每�ơ调用完毕，�~�译器给esp加了多少�Q�就手动减多��。（�~�译器不一定会生成 call xxxx; add esp, xx�q�样的代码，通过改函数返回地址�Q�忽略后面的add esp, xx指��o是很�p�糕的做法。）

call_redirect

flyinghearts 2012-08-05 21:02 发表评论

flyinghearts — Tue, 15 May 2012 12:26:00 GMT

下蝲�Q?a href="/Files/flyinghearts/peekmsg.7z" title="peekmsg">peekmsg

用法�Q?br />     peekmsg.exe   游戏�ȝ��?br />     或用lordpe�Q�打开游戏�ȝ��序，导入peekmsg.dll中的init

原理�Q?br />       hook PeekMessage函数�Q�用Sleep、WaitForMultipleObjects�{�函数让出CPU旉��片�?

flyinghearts 2012-05-15 20:26 发表评论

三国�?剧本修改�?1.2

flyinghearts — Tue, 15 May 2012 12:14:00 GMT

内置剧本改�ؓ加强版剧本，保存剧本�Ӟ��同时生成普通版/加强版剧本�?br />�Q�没旉��试�Q�可能在更改宝物所有者时�Q�会有一些bug�Q?br />
三国�?剧本修改�?.2

flyinghearts 2012-05-15 20:14 发表评论

flyinghearts — Fri, 30 Mar 2012 12:16:00 GMT

前几天在水母上看到的题：

正常的比�?assert(-1 < 1U) 是会��p�|的。因�?-1 会提升成无符��h��?br />写一个安全的比较函数�Q��?br />template
int SafeIntCompare(T1 i1, T2 i2);
如果 i1 真实�?< i2�Q�返�?-1
     i1 真实�?== i2�Q�返�?nbsp; 0
     i1 真实�?> i2�Q�返�?nbsp; 1

只有当两个类型一个是有符受��另一个是无符��h��Q�才需要特�D�处理�?br />对类型的�W�号判断�Q�可以直接判断该�c�d��?1是否�?��，也可以用标准库std::numeric_limits中的is_signed成员�?br />
��单的做法�Q?br />
template<typename T1, typename T2>
int SafeIntCompare(T1 v1, T2 v2)
{
  static const bool t1 = std::numeric_limits<T1>::is_signed;
  static const bool t2 = std::numeric_limits<T2>::is_signed;
  if (t1 != t2) {
    if (t1 && v1 < 0) return -1;
    if (t2 && v2 < 0) return 1;
  }
  if (v1 == v2) return 0;
  if (v1 < v2)  return -1;
  return 1;
}

但由于进行比较的两个数可能分别是�Q�有�W�号数和无符��h��Q�编译时�~�译器会�l�出大量的警告�?br />
     要避免有�W�号数和无符��h��的进行直接比较，��必��d��它们都�{为同一个类型T。这个类型的��定可以采用两种�Ҏ��Q?br />
     1 比较原来两个�c�d��是否是有�W�号��C��及它们所占用的字节数�Q�来推断出应该将它们都�{为哪�U�类型T�Q�这是vc那个safeint的做法�?br />
   2 采用�q�个trick�Q�将�q�两个类型的敎ͼ�数可以取0�Q�直接相加，得到的结果的�c�d��是所求的。这是因为：两个数进行比较时�Q�采用的�c�d��转换规则和两个数相加时所采用的规则是一致的�?br />

�Ҏ��后的代码

但上面的写法有一个问题：如果一�?short和一个unsigned char�q�行比较�Q�编译器都是转�ؓint�q�行比较�Q�没有必要进行特�D�处理（上面的代码处理后会多一个与0的比较）。实际上�Q�如果两个类型都是�{为有�W�号�c�d��Q�可以直接进行比较�?/div>最�l�代码：

template<typename T>
struct IsSigned {
  static const bool value = T(-1) < T(0);
};

template<bool> struct Assert {};
template<> struct Assert<false>;

template<int> struct Type {};
typedef Type<0> TagNormal;
typedef Type<1> TagFirstArgIsSigned;
typedef Type<2> TagSecondArgIsSigned;

template<typename T1, typename T2, typename T3>
int SafeIntCompare(T1 v1, T2 v2, T3, TagNormal)
{
  if (v1  < v2) return -1;
  if (v1 == v2) return 0;
  return 1;
}

template<typename T1, typename T2, typename T3>
int SafeIntCompare(T1 v1, T2 v2, T3 v3, TagFirstArgIsSigned)
{
  if (v1 < 0) return -1;
  return SafeIntCompare(T3(v1), T3(v2), v3, TagNormal());
}

template<typename T1, typename T2, typename T3>
int SafeIntCompare(T1 v1, T2 v2, T3 v3, TagSecondArgIsSigned)
{
  if (v2 < 0) return 1;
  return SafeIntCompare(T3(v1), T3(v2), v3, TagNormal());
}

template<typename T1, typename T2, typename T3>
int SafeIntCompare(T1 v1, T2 v2, T3 v3)
{
  typedef std::numeric_limits<T1> M1;
  typedef std::numeric_limits<T2> M2;
  typedef std::numeric_limits<T3> M3;
  static const bool is_arg_valid = M1::is_integer & M2::is_integer;
  Assert<is_arg_valid>();
  static const int type_idx = M3::is_signed ? 0 : (M1::is_signed + M2::is_signed * 2) % 3;
  return SafeIntCompare(v1, v2, v3, Type<type_idx>());
}

template<typename T1, typename T2>
int SafeIntCompare(T1 v1, T2 v2)
{
  return SafeIntCompare(v1, v2, T1(0) + T2(0));
}

flyinghearts 2012-03-30 20:16 发表评论

面试题精�?目录

flyinghearts — Sun, 18 Mar 2012 14:24:00 GMT

�?nbsp; �?/div>

面试题精解之一�Q?二叉�?/a>
1 求二叉树中相距最�q�的两个节点之间的距��?br /> 2 判断二叉树是否��^衡二叉树
3 指定二叉树，�l�定两节�Ҏ��其最�q�共同父节点
4 二叉树的�q�度遍历、逐层打印二叉树节�Ҏ��据、只打印某层节点数据
5 在二叉树中找出和�Q�叶子到根节点�\径上的所有节点的数据和）为指定值的所有�\径�?br /> 6 ��二叉查找树转�ؓ有序的双链表
7 求二叉树的镜�?br /> 8 二叉树前序、中序、后序遍历的非递归实现
9 求二叉树高度的非递归实现
10 �q�接二叉树同一层上的结�?/div>

面试题精解之二：字符丌Ӏ�数�l�（1�Q?/a>

1 在一个字�W�串中找到第一个只出现一�ơ的字符�Q�如输入abac�Q�则输出b�?br /> 2 输出字符串的所有组合，�?abc"输出a、b、c、ab、ac、bc、abc�?br /> 3 �Ҏ��条�g扑և�两个数�?br />   ① 数组中，除了两个数字出现奇数�ơ外�Q�其它数字都出现偶数�ơ，扑և��q�两个数字：
   ② 长度为n的数�l�，由数�?到n�l�成�Q�其中数字a不出玎ͼ�数字b出现两次�Q�其它的数字恰好出现一�ơ�?br />       在不修改原数�l�的情况下，扑և�数字a和数字b�?br /> 4 求数�l�（或环状数�l�）的最大连�l�（或不�q�箋�Q�子序列和�?br />

flyinghearts 2012-03-18 22:24 发表评论

flyinghearts — Sun, 18 Mar 2012 13:28:00 GMT
     摘要: 面试题精解之二：字符丌Ӏ�数�l�（1�Q? 本篇文章发表在下面三个博客中�Q�如果出现排版问题，��L��步到另一个博客�?http://www.shnenglu.com/flyinghearts http://www.cnblogs.com/flyinghearts http://blog.csdn.net/flyinghearts 1   ...  阅读全文

flyinghearts 2012-03-18 21:28 发表评论

flyinghearts — Sun, 18 Mar 2012 13:16:00 GMT

先看一道面试题�Q?/span>

长度�?/span>n的数�l�，由数�?/span>1�?/span>n�l�成�Q�其中数�?/span>a不出玎ͼ�数字b出现两次�Q�其它的数字恰好出现一�ơ。怎样通过只读遍历一�ơ数�l�，扑և�数字a�?/span>b�?/span>

�׃��只能遍历一�ơ，在遍历数�l?/span>arr�Ӟ��出 a�?/span>b的差��|��以及a�?/span>b的��^方差�Q�通过解方�E�，卛_��求得a�?/span>b。具体做法�ؓ�Q?/span>

设：

      s1 = 1 + 2 + ... + n           (= n * (n + 1) / 2)

      s2 = arr[0] + arr[1] + ... + arr[n - 1]



      r1 = 1 + 4 + ... + n^2          (= n * (n + 1) * (2 * n + 1) / 6)

      r2 = arr[0]^2 + arr[1]^2 + ... + arr[n - 1]^2



     c = a - b = s1 - s2

     d = a^2 - b^2 = r1 - r2

    昄��Q?/span> a + b = (r1 - r2) / (s1 - s2)

�Ҏ��a+b的值和a-b的��|��很容易就可算�?/span>a�?/span>b�?/span>

��法虽然��单，但实现�v来，却有一个很大问题：计算 s1�?/span>s2�?/span>r1�?/span>r2�q?/span>4个数�Ӟ��计算�q�程中可能出现溢出，造成�l�果不准。由于最�l�目的是��Z��计算�?/span>c�?/span>d�Q�一个改�q�的�Ҏ��是：

c = s1 - s2 = (1 - arr[0]) + (2 - arr[1]) + ... + (n - arr[n - 1])

d = (1 - arr[0]^2) + (4 - arr[1]^2) + ... + (n^2 - arr[n - 1]^2)

但这��L��做法�Q��ƈ不能解决问题�Q?/span>n�E�微大点�Q�照样存在溢出问题�?/span>

那么怎样才能避免计算溢出呢？�{�案很简单，用模�q�算�Q?/span>每进行一�ơ加减运��时�Q�都取结果�ؓ原结果除以一个��够大的常�?/span>M的余数。这样加减运��中�Q�就不会现现溢出问题。最后再�?/span> c % M�?/span>d % M�Q�推��出c�?/span>d的具体倹{��比如说�Q�计��?/span>s2改�ؓ计算�Q?/span>

   s2 % M = ((((arr[0] % M) + arr[1]) % M + ...) % M + arr[n - 1]) %M

从表面上看，采用模运��后�Q�计��量会增加很多。但实际上，�?/span>M取合适的值时�Q�计��量�q�不会增加！�Q?/span>

先回��下计算机基本知识：两个�?/span>N位（寄存器�ؓN位）的二�q�制无符��h��?/span>a�?/span>b相加�Q�若�l�果溢出了，CPU会怎么处理�Q�当然是��溢出的那一位忽略掉�Q�可能还要设�|�下溢出标志�Q�，得到的结果实际上是：(a + b) mod 2^N�?strong>无符��h��间的��术�q�算�Q�本质上��是模运��?/span>。现在的CPU�?strong>采用二补数来表示负整敎ͼ�本质上也是运用模�q�算�Q�教�U�书��二补数表示的负整数��单定义�ؓ�Q�对正整数取反后�?/span>1�Q�，�q�与无符��h��间的�q�算是一致的�Q�在实现上，比用其它�Ҏ��Q�比如说一补数�Q�表�C��整数�Q�要优美易实现�?/span>

�?/span>32位��^��C��Q?/span> -x mod 2^32 = 2^32 – x (x > 0)�Q?/span>

因�?/span>-1的二�q�制表示��是�Q?/span>0xFFFFFFFF

了解了这些，��׃��会奇�?/span>C/C++标准的规定：无符��h��间的�q�算是模�q�算不会溢出�Q�有�W�号数�{为无�W�数�Q�采用模�q�算后的倹{��（��Z��兼容没采用二补数的机器，无符��h��转�ؓ有符��h��Ӟ��若无�W�号数的数��D��Z��有符��h��可表�C�的范围�Q�结果是�q�_��相关的。）

因而，在对32�?/span>CPU�q�_��Q�可以先��有�W�号数�{为无�W�号敎ͼ�再取M = 2 ^32。需要特别注意的是，应该采用多少位的无符��h��保存计算中用到的数��|��如何避免模运��可能带来的问题�Q?/span>

①　无符��h��c�d��的选择�Q?/span>

a�?/span>b的取��D��围�ؓ�Q?/span>[1, n]�Q?/span>

c % M = (a - b) % M 的取��D��围�ؓ�Q?/span>[1, n] (a > b�?/span>)�Q?/span> [M - n, M - 1] (a < b�?/span>)

�q�两个范围不能重叠，而因 n < M - n �?/span> 2 * n < M

�?/span> M�?/span>2^32的话�Q�且 n < 2^31�Q?/span> 可以采用32位无�W�号数表�C?/span>c的倹{�?/span>

�Ҏ��c % M值在哪一个范��_��可以��定a > b�q�是a < b�Q?/span>

�׃��q�算�q�程中都是采用无�W�号数计��，�?/span> a < b�Ӟ��必须�q�行如下调整�Q?/span>

c % M 调整�?/span> (-c) % M

d % M 调整�?/span> (-d) % M

�q�样才能保证�l�果的正��性�?/span>

② 用公式计��所有数字的和、��^方和�Ӟ��可能出现的问题：

模运��满��I�� (a * b) % M = ((a % M) * (b % M)) % M

�?strong>不满��?/strong>�Q?/span> (a / b) % M = ((a % M) / (b % M)) % M

在计��?/span> (n * (n + 1) / 2) % M�Ӟ�� 不能写成�Q?/span>

s = ((n * (n + 1)) % M / 2) % M�Q?/span>

而应该写成：

if (n % 2 == 0) s = ((n / 2) * (n + 1)) % M

else s = (((n + 1) / 2) * n) % M

或者：s = (INT((n + 1) / 2) * (n + (n + 1) % 2)) % M �Q�其�?/span>INT(x)为取��数x的整数部份）�?/span>

完整代码�Q?/span>

#include <climits>
#include <cassert>

#define SMALL_ARRAY 0

struct Pair {
  int zero;
  int twice;
};

//32位CPU�q�_��Q�长度n一定小�?^16�ơ方�Ӟ��表示一个数的��^方��|��可用32位无�W�号数类型，效率很高�?br />//长度n若在[2^16, 2^31]区间�Q�就必须用到64位无�W�号数类型，效率较高�?br />//长度n若在[2^31, 2^32)�Ӟ��表示所有数的和sum�Q�就必须改用64位无�W�号数类型，效率不高�?nbsp;
Pair find_number(const int arr[], unsigned len)
{
  const unsigned bits = CHAR_BIT * sizeof(unsigned);
#if SMALL_ARRAY
  const unsigned max_len = 1u << (bits / 2u);
  typedef unsigned int uint;
#else
  const unsigned max_len = 1u << (bits - 1);
  typedef unsigned long long uint;
#endif

  assert(arr && len >= 2 && len < max_len);
  const unsigned* const data = (const unsigned*)arr;
  unsigned sum = 0;
  uint square_sum = 0;
  for (unsigned i = 0; i < len; ++i)  {
    const unsigned value = data[i];
    sum += value;
    square_sum += (uint)value * value;     //注意两个数的乘积是否会溢�?nbsp;
  }

  //1 + 2 + 3 +  + len = len * (len + 1) / 2
  const uint sum_all = (len + 1) / 2u * (uint)(len + (len + 1) % 2u);

  //1^2 + 2^2 + 3^2 +  + len^2 = len * (len + 1) * (2 * len + 1) / 6
  const unsigned len2 = 2u * len + 1;
  const uint square_sum_all = len2 % 3u == 0 ? len2 / 3u * sum_all : sum_all / 3u * len2;

  unsigned difference = (unsigned)sum_all - sum;
  uint square_difference = square_sum_all - square_sum;
  const bool is_negative = difference > INT_MAX;

  if (is_negative) {
    difference = -difference;
    square_difference = -square_difference;
  }

  assert(difference != 0 && square_difference % difference == 0);
  const unsigned sum_two = square_difference / difference;

  assert((sum_two + difference) % 2u == 0);
  const unsigned larger  = (sum_two + difference) / 2u;
  const unsigned smaller = (sum_two - difference) / 2u;

  if (is_negative) {
    const Pair result = { smaller, larger};
    return result;
  }
  const Pair result = { larger, smaller};
  return result;
}

int main()
{

}

flyinghearts 2012-03-18 21:16 发表评论

Fibonacci数计��中的两个思维盲点及其扩展数列的通用高效解法

flyinghearts — Tue, 28 Feb 2012 14:14:00 GMT

摘要: http://www.shnenglu.com/flyingheartshttp://www.cnblogs.com/flyingheartshttp://blog.csdn.net/flyingheartspdf版本下蝲㈠　Fibonacci�?刚接触Fibonacci数的时候，在网上看�?#8220;矩阵�?#8221;�Q�看到要先实��C��个矩阵乘法，感觉太麻烦了。后来仔�l�观察Fibonacci数列... 阅读全文

flyinghearts 2012-02-28 22:14 发表评论

flyinghearts — Tue, 28 Feb 2012 12:54:00 GMT

摘要: 面试题精解之一�Q?二叉�? 本篇文章发表在下面三个博客中�Q�如果出现排版问题，��L��步到另一个博客�?http://www.shnenglu.com/flyinghearts http://www.cnblogs.com/flyinghearts http://blog.csdn.net/flyinghearts 1 求二叉树中相... 阅读全文

flyinghearts 2012-02-28 20:54 发表评论

flyinghearts — Fri, 23 Sep 2011 11:45:00 GMT

喝汽水问�?/span>

by flyinghearts

�?/span>1000瓶汽��_��喝完后每3个空瓶能�?/span>1瓶汽��_��问最后最多可以喝几瓶汽水�Q�此时剩余几个空�Ӟ��

不妨假设�Q�共�?/span>n瓶汽��_��?/span>a个空瓶能�?/span>b瓶汽��_��a > b�Q��?/span>刚开始有n瓶汽��_��喝完后就�?/span>n个空�Ӟ��多喝的汽水是靠空瓶换来的�Q?strong>每进行一�ơ空瓶换汽水�Q�就能多�?/span>b瓶汽水、空瓶数目就减少�?/span>a-b�?/span>�Q?/span>a个空瓶换�?/span>b瓶汽��_��喝完后得�?/span>b个空�Ӟ��?/span>

(下面�?/strong> [x] 表示x的整数部�?/span>)

1 如果允许从别处（老板或其他顾客处�Q�借空�Ӟ��当然�Q�有借有�q�）

�I�瓶换汽水次敎ͼ� [n / (a - b)]

最后剩余空�Ӟ�� n % (a - b)

��d��可以喝到汽水�Q?/span> n + [n / (a - b)] * b

2 不允许借空�?/span>

�I�瓶换汽水过�E�中�Q?strong>一但空瓶数��于a�Q�则停止交换�?/span>

�?/span> n < a�Q�显�Ӟ��I�瓶换汽水次��Cؓ0�Q��d��可以喝到汽水n�Ӟ��最后剩余空�?/span>n�?/span>

�?/span> n >= a�Q�（下面提供三种解法�Q?/span>

解法一 �I�瓶换汽水次�?/span>k�{�于满��n – (a-b)*t < a的最��非负整�?/span>t:

t > (n-a)/(a-b)�Q�最��的t�?/span> [(n-a)/(a-b)] + 1 = [(n-b)/(a-b)]

剩余的空瓶数�Q?/span>n – (a-b)*t

= n – (a-b)*([(n-b)/(a-b)])

= b + (n-b) - (a-b)*([(n-b)/(a-b)])

= b + (n-b)%(a-b)

解法�?/span> 先预�?/span>a个空�Ӟ��剩余的n-a个空瓶进行换汽水�Q�换的过�E�中�Q�若�I�瓶不够a个，则从预留�?/span>a个空瓶中“�?#8221;�Q�因而，

�I�瓶换汽水次敎ͼ�[(n-a)/(a-b)] + 1 = [(n-b)/(a-b)]�Q�预留的a个空瓶也能换一�ơ）

最后剩余空�Ӟ�� (n-b) % (a-b) + b�Q�预留的a个空瓶换�?/span>b瓶汽��_��

解法�?/span> 最后一�ơ空瓶换汽水得到�?/span>b瓶汽��_��喝完后得�?/span>b个空�Ӟ��因而最后剩余空瓶数必然大于b个，先预�?/span>b个空�Ӟ��剩余的n-b个空瓶进行换汽水�Q�若�I�瓶不够a个，则从预留�?/span>b个空瓶中“�?#8221;�Q�由于能�q�行�I�瓶换汽��_��I�瓶�?/span>>= a – b�Q�因�?#8220;�?#8221;完后�Q�可以保证空瓶数大等�?/span>a�Q�，

�I�瓶换汽水次敎ͼ�[(n-b)/(a-b)]�Q?/span>

最�l�剩余空瓶数�Q?/span>b + (n-b) % (a-b)

�Q�对解法三，n>=b时结论成立，对解法一、二�Q�可以验�?/span>n >=b�Ӟ��l�论也成立）

因而，�?/span> n >= b

�I�瓶换汽水次敎ͼ� [(n-b)/(a-b)]

最后剩余空�Ӟ�� b + (n-b) % (a-b)

��d��可以喝到汽水�Q?/span> n + [(n-b)/(a-b)] * b

对原题：

n = 1000�Q?/span>a = 3, b = 1�Q?/span> a – b = 2

若允许借空�?/span>

可以喝到汽水�Q?/span> 1000 + 1000 / 2 = 1500

剩余�I�瓶�Q?/span>1000 % 2 = 0

若不允许借空�?/span>

可以喝到汽水�Q?/span> 1000 + (1000 - 1) / 2 = 1499�Q?/span>

剩余�I�瓶�Q?/span> 1 + (1000 - 1) % 2 = 2

flyinghearts 2011-09-23 19:45 发表评论

三国�?剧本修改�?1.1

flyinghearts — Sun, 07 Aug 2011 15:24:00 GMT

�l�以前写的剧本修改器�Q�加了个界面�Q�本想用wtl�Q�但是代码中用到不少“初始化列�?#8221;�{�c++11新特性，只好让VC2010靠边站了。对mingw�Q�好用的gui库还真没有，��x��十几个消息�Q�干脆直接调用windows api得了�?br />
flyinghearts 2011-08-07 23:24 发表评论

对环状数�l�求�q�箋子数�l�的最大和

flyinghearts — Wed, 20 Jul 2011 15:49:00 GMT

思�\�Q�由于数�l�元素��d��是固定��|��因而跨头、尾的连�l�子数组和最大，�{��h于求中间那段和最��。因此，问题转�ؓ计算 �q�箋子数�l�的最大和 �?�q�箋子数�l�的最��和

import std.algorithm;

int ring_max_continue_sum(in int[] src)

{

int min_sum = src[0], cur_min_sum = min_sum;

int max_sum = src[0], cur_max_sum = max_sum;

int total_sum = src[0];

foreach (value; src[1 .. $]) {

cur_min_sum = min(value, cur_min_sum + value);

min_sum = min(min_sum, cur_min_sum);

cur_max_sum = max(value, cur_max_sum + value);

max_sum = max(max_sum, cur_max_sum);

total_sum += value;

}

return max(max_sum, total_sum - min_sum);

}

unittest {

auto ta = [3, -2, 3];

auto tb = [3, 4, -2, 3, -7, 1, -3, 8];

assert(ta.ring_max_continue_sum == 6);

assert(tb.ring_max_continue_sum == 16);

}

void main()

{

}

flyinghearts 2011-07-20 23:49 发表评论

最短摘要的生成�Q�补充）

flyinghearts — Wed, 20 Jul 2011 15:39:00 GMT

摘要: 把另一�U�解法也贴出来吧�Q�由于题目的背景是在大量数据中查扑ְ�数关键字�Q�效率不如前面的解法�Q�。基本思�\�Q�将关键�?�?开始编��P�� 对分词后源词�l�，�q�行映射�Q�如果是关键字，��映��ؓ该关键字的编��P��否则映射为数�?用两个指针，一前一后，很容易就可以实现在O(n)旉��内找出结果。Code highlighting produced by Actipro CodeHighlighter (freeware)... 阅读全文

flyinghearts 2011-07-20 23:39 发表评论

Fibonacci数列的两�U�O(lgn)解法

flyinghearts — Wed, 20 Jul 2011 15:30:00 GMT

import std.stdio : writef;

uint fib_matrix(uint num) // 矩阵法求fibonacci�?/span>

{

if (num <= 1) return num;

--num;

uint ret = 1, next = 1;

for (uint a = 1, b = 0; num != 0; num >>= 1) {

if (num & 1) {

auto tmp = next;

next = (a + b) * next + a * ret;

ret = a * tmp + b * ret;

}

auto tmp = a;

a = a * (a + 2 * b);

b = b * b + tmp * tmp;

}

return ret;

}

uint fib(uint num)

{

if (num <= 1) return num;

uint left_most_one = num; //��等于num的最�?的k�ơ幂

for (uint value = num; value &= (value - 1); ) left_most_one = value;

uint ret = 1, next = 1;

while (left_most_one >>= 1) {

if (num & left_most_one) {

auto tmp = ret;

ret = ret * ret + next * next;

next = (tmp * 2 + next) * next;

} else {

auto tmp = ret;

ret = (next * 2 - ret) * ret;

next = tmp * tmp + next * next;

}

return ret;

}

uint fib_basic(uint num)

{

if (num <= 1) return num;

uint prev = 0, current = 1;

for (uint i = 2; i <= num; ++i) {

auto tmp = prev;

prev = current;

current += tmp;

}

return current;

}

unittest {

foreach (i; 0 .. 48) {

auto a = fib_basic(i), b = fib_matrix(i), c = fib(i);

if (a != b || a != c)

writef("%s %s %s %s\n", i, a, b, c);

}

void main()

{

}

flyinghearts 2011-07-20 23:30 发表评论

flyinghearts — Tue, 19 Jul 2011 14:07:00 GMT

　　晚上惌��个程序，�l�果VC 2010头一�ơ�Ş工：　
cl: 命��o�?error D8027 :无法执行“E:\prog\vc2010\bin\c1xx.dll”
上网搜烦了下�Q�也没找��C��个解��x��法（官方说明�Q�。正郁闷着�Q�突焉��惛_��cl.exe可以正常�q�行�Q�而c1xx.dll不能正常�q�行�Q�会不会是c1xx.dll的依赖库出问题了�Q�于是调出dependency一查，果然��了个msvcp100.dll�Q�估计是某个卸蝲软�g造成的）�Q�从别处拯��一个到bin目录�Q�问题解冟�?br />

flyinghearts 2011-07-19 22:07 发表评论

久久无码人妻一区二区三区,欧美亚洲日本久久精品,久久久久久国产精品无码下载

mingw gcc的头文�g存在�l�构定义错误�Q�！

c++11 最反直觉的地方

三国�?剧本修改�?1.2

面试题精�?目录

Fibonacci数计���中的两个思维盲点及其扩展数列的通用高效解法

三国�?剧本修改�?1.1

对环状数�l�求�q�箋子数�l�的最大和

最短摘要的生成�Q�补充）

Fibonacci数列的两�U�O(lgn)解法

Fibonacci数计��中的两个思维盲点及其扩展数列的通用高效解法