gcd.c
上传用户:zhongxx05
上传日期:2007-06-06
资源大小:33641k
文件大小:2k
源码类别:

Symbian

开发平台:

C/C++

  1. /* ***** BEGIN LICENSE BLOCK ***** 
  2.  * Version: RCSL 1.0/RPSL 1.0 
  3.  *  
  4.  * Portions Copyright (c) 1995-2002 RealNetworks, Inc. All Rights Reserved. 
  5.  *      
  6.  * The contents of this file, and the files included with this file, are 
  7.  * subject to the current version of the RealNetworks Public Source License 
  8.  * Version 1.0 (the "RPSL") available at 
  9.  * http://www.helixcommunity.org/content/rpsl unless you have licensed 
  10.  * the file under the RealNetworks Community Source License Version 1.0 
  11.  * (the "RCSL") available at http://www.helixcommunity.org/content/rcsl, 
  12.  * in which case the RCSL will apply. You may also obtain the license terms 
  13.  * directly from RealNetworks.  You may not use this file except in 
  14.  * compliance with the RPSL or, if you have a valid RCSL with RealNetworks 
  15.  * applicable to this file, the RCSL.  Please see the applicable RPSL or 
  16.  * RCSL for the rights, obligations and limitations governing use of the 
  17.  * contents of the file.  
  18.  *  
  19.  * This file is part of the Helix DNA Technology. RealNetworks is the 
  20.  * developer of the Original Code and owns the copyrights in the portions 
  21.  * it created. 
  22.  *  
  23.  * This file, and the files included with this file, is distributed and made 
  24.  * available on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 
  25.  * EXPRESS OR IMPLIED, AND REALNETWORKS HEREBY DISCLAIMS ALL SUCH WARRANTIES, 
  26.  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS 
  27.  * FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 
  28.  * 
  29.  * Technology Compatibility Kit Test Suite(s) Location: 
  30.  *    http://www.helixcommunity.org/content/tck 
  31.  * 
  32.  * Contributor(s): 
  33.  *  
  34.  * ***** END LICENSE BLOCK ***** */ 
  35. #include "gcd.h"
  36. /* calculate the gcd of the input arguments. Taken from Knuth, TAOCP Vol. 2 */
  37. signed long gcd(signed long u, signed long v)
  38. {
  39.     int k = 0 ;
  40.     signed long t ;
  41.     while (!((u | v) & 1)) /* while both u and v are even */
  42.     {
  43.         u >>= 1 ; v >>= 1 ; k++ ;
  44.     }
  45.     t = (u & 1) ? -v : u ;
  46.     do {
  47.         /* Halve t until it is odd */
  48.         while (!(t & 1)) t >>= 1 ;
  49.         /* Replace the larger of u and v by |t|, except perhaps
  50.            during the first time this step is performed */
  51.         if (t > 0) u =  t ;
  52.         else       v = -t ;
  53.         t = u-v ;
  54.     }
  55.     while (t!=0) ;
  56.     /* return u * 2^k */
  57.     return (u << k) ;
  58. }